CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
user4892930
user4892930

Reputation: 41

Finding Big-O of this code

I need some help finding the complexity or Big-O of this code. If someone could explain what the Big-O of every loop would be that would be great. I think the outter loop would just be O(n) but the inner loop I'm not sure, how does the *=2 effect it? 

k = 1;

do
{
   j = 1;
   do
   {
      ...
      j *= 2;
   } while (j < n);

   k++;
} while (k < n);

Upvotes: 1

Views: 82

Answers (2)

GokulSrinivas
GokulSrinivas

Reputation: 383

The inner loop always runs from j=1 to j=n.

For simplicity, let's assume that n is a power of 2 and that the inner loop runs k times.

The values of j for each of the k iterations are,

j = 1
j = 2
j = 4
j = 8
.... 
j = n
// breaks from the loop

which means that 2^k = n or k = lg(n)

So, each time, it runs for O(lg(n)) times.

Now, the outer loop is executed O(n) times, starting from k=1 to k=n.

Therefore, every time k is incremented, the inner loop runs O(lg(n)) times.

k=1 Innerloop runs for : lg(n)
k=2 Innerloop runs for : lg(n)
k=3 Innerloop runs for : lg(n)
...
k=n Innerloop runs for : lg(n)
// breaks from the loop

Therefore, total time taken is n*lg(n)

Thus, the time complexity of this is O(nlg(n))

Upvotes: 1

Jacob Ritchie
Jacob Ritchie

Reputation: 1401

The outer loop runs O(n) times, since k starts at 1 and needs to be incremented n-1 times to become equal to 1.

The inner loop runs O(lg(n)) times. This is because on the m-th execcution of the loop, j = 0.5 * 2^(m).

The loop breaks when n = j = 0.5 * 2^m. Rearranging that, we get m = lg(2n) = O(lg(n)).

Putting the two loops together, the total code complexity is O(nlg(n)).

Logarithms can be tricky, but generally, whenever you see something being repeatedly being multiplied or divided by a constant factor, you can guess that the complexity of your algorithm involves a term that is either logarithmic or exponential.

That's why binary search, which repeatedly divides the size of the list it searches in half, is also O(lg(n)).

Upvotes: 4

Related Questions