CODEWITHSUNDEEP
algorithmtime-complexitybig-o
bobthecoder123
bobthecoder123

Reputation: 25

Time complexity for a nested for loop

Given the following nested for loop:

for (int i=n; i>1; i=i/2):
    for (int j=i; j<n; j=j*2)
        # O(1) expression

What would the time complexity of the entire loop be? My answer is O(log(n)*log(n)) but I'm not sure if it is right.

Upvotes: 0

Views: 97

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

This is a great place to use the maxim

When in doubt, work inside out!

That is, start by taking the innermost loop and replacing it with an expression indicating how much work it's doing, then repeat this until you're done.

In your case, the innermost loop is

for (int j=i; j<n; j=j*2)
    # O(1) expression

Now, how much work does this do? To answer that, let's think about how the loop works. On each iteration, the value of j doubles from what it was before. Since j begins at i, the values that j takes on will be i, 2i, 4i, 8i, etc., and more generally on the kth iteration of the loop the value of j will be 2k·i. The loop terminates once this value is equal to or exceeds n, which happens when

2k · i = n

2k = n / i

k = lg(n / i)

So this means we're going to run the loop for Θ(log (n / i)) iterations. If we substitute this into the original loop, we're left with this code:

for (int i=n; i>1; i=i/2):
    Do Θ(log (n / i)) work;

So how much overall work does that end up being? Well, the outer loop will run once with i = n, then once with i = n/2, then once with i = n/4, etc., so the total work done is

Θ(log (n/n) + log(n/(n/2)) + log(n/(n/4)) + ... + log(n / 1))

= Θ(log 1 + log 2 + log 4 + log 8 + ... + log n)

= Θ(log 20 + log 21 + log 22 + log 23 + ... + log 2log n)

Θ(0 + 1 + 2 + ... + log n)

Remember that 0 + 1 + 2 + ... + k = k(k + 1) / 2 = Θ(k2), so the total work done here is

Θ(0 + 1 + 2 + ... + log n)

= Θ(log2 n).

The key techniques in arriving at this answer were starting from the inside, connecting logarithms with the number of loop iterations performed when repeatedly doubling something in size, and the formula for 1 + 2 + ... + k.

Upvotes: 1

Related Questions