CODEWITHSUNDEEP
algorithmbig-o
ThatOneGoi
ThatOneGoi

Reputation: 29

What would be the time complexity of this code?

What would be the time complexity of this code?

i = n;
  while(i > 1) {
    j = i;
    while (j < n) {
      k = 0;
      while (k < n) {
        k = k + 2;
      }
      j = j * 2;
    }
    i = i / 2;
  }

I tried analyzing this code and got a complexity of Log^2n * n I rewrote the code in a for loop format to make it easier to see which came out like this. 

for (i = n; i > 1; i = i / 2) // log2n + 1
  {
    for(j = i; j < n; j = j * 2) // log2n + 1
    {
      for (k = 0; k < n; k = k + 2)  // n + 1 times
      {
          cout << "I = " << i << " J = " << j << " and K = " << k << endl;
      }
      cout << endl;
    }
  }

Is that correct? If not, why? I am new to algorithms and trying to understand but don't know where else to ask, sorry.

Upvotes: 0

Views: 51

Answers (1)

David G
David G

Reputation: 96855

Yes, your answer is correct. The variable i is halved at every step, making the outer loop O(log n). j doubles at every step, making that loop O(log n), and the innermost k loop increases linearly, making that loop O(n). Multiplying together gives O(n log² n).

Upvotes: 1

Related Questions