CODEWITHSUNDEEP
time-complexitybig-o
Kiarash
Kiarash

Reputation: 23

What is the time complexity of this nested loop where the inner loop grows by a factor of the outer?

What is the time complexity of the second loop?

 for(int i =1; i<=n;i++)
   {
    for(int j=i ; j<=n; j+=i*2);
   }

I have gone this far:

i=1 ==> j=n/2
i=2 ==> j=(n-1)/4
i=3 ==> j=(n-2)/6
i=4 ==> j=(n-3)/8
i=n ==> j=1/2n

but i cant find any algorithm for this series!!

Upvotes: 1

Views: 301

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

Let's use the time-tested technique of

When in doubt, work inside out!

We have this loop nest:

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i*2) {
        /* ... do nothing ... */
    }
}

We'll begin by taking aim at that inner loop, the one shown here:

for (int j = i; j <= n; j += i*2) {
    /* ... do nothing ... */
}

We begin with j = i. On the next iteration we have j = 3i, on the next iteration we have j = 5i, etc. We stop once we get to j = n, which means that we have to increase j from i to n taking steps of size i. This means that the total number of iterations is (n - i) / 2i = n / 2i - 1. Of course, this isn't strictly speaking correct because we need to account for integer division, which we can account for by adding one to that number to indicate "and we might need one more trip through the loop." Therefore, the number of iterations of this loop is bounded nicely by n / 2i, which is Θ(n / i).

We can therefore replace that loop with "do Θ(n / i) work," giving us this simpler loop nest:

for (int i = 1; i <= n; i++) {
    do Θ(n / i) work;
}

To finish things up, we just need to add this up across all the loop iterations. Notice that on the first loop iteration we're doing (roughly) n/1 work, then on the second we're doing n/2 work, then n/3, then n/4, etc. And more generally, the total work done here will be (asymptotically) equal to

n/1 + n/2 + n/3 + n/4 + ... + n/n

= n(1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n)

You might recognize that last summation as the first n terms of the harmonic series. Mathematically, we abbreviate this number as Hn, and so the total work done here is (roughly) nHn.

It's known that Hn = Θ(log n), which means that the work done by this loop is Θ(n log n). This tracks with @RichardCritten's comment that the runtime is pretty close to n, which is the case with a runtime of Θ(n log n) (it grows ever so slightly more quickly than n).

Hope this helps!

Upvotes: 2

lorro
lorro

Reputation: 10880

The loop repeats floor((n - i + 1) / (2 * i)) times. Therefore, if the body is O(1), the complexity is floor((n - i + 1) / (2 * i)).

When we discuss time complexity, we usually omit the constant factor (hence the ordo notation). So this can be simplified to O(n/(2i) - 1/2 + 1/(2i)) = O(n/i). If the body is not const, you need to multiply it accordingly.

Note that it depends on both i and n. If you're interested in the complexity of the external loop, not the internal, you need to sum it over the possible i values.

Upvotes: 0

Related Questions