Complexity of a nested geometric sequence

Question

Below code is actually limited to O (n ^ 2), can anyone explain why?

for (int i = 1; i < n; i++) {
    int j = i;
    while (j < n) {
        do operation with cost O(j)
        j = j * 3;
    }
}

+3

timecomplexitttt June 19 15 at 10:28

3 answers

Ami tavory · Answer 1 · 2015-06-19T10:35:57+0000

It's not that hard.

Your internal loop complexity forms a geometric progression with a total of O (n).

Without filling in all the details (this looks like an HW problem), note that the formula for the geometric sequence is

a_0 (q ^ k - 1) / q - 1, (a_0 = first element, q = multiplication factor, k = num elements).

and your q ^ k is O (n) here.

Your outer loop is O (n).

Since it is a nested loop and the inner member is independent of the outer index, you can multiply it.

Aditya adusumalli · Answer 2 · 2015-06-20T06:52:58+0000

The proof is a geometric progression :)

For i = n, the inner loop is not executed more than once if i> n / 3 (because in the next iteration j is> = n).
So, for 2n / 3 iterations of the outer loop, the inner loop repeats only once and performs an O (j) operation. So for 2n / 3 iterations the complexity is O (n ^ 2).
To calculate the complexity of the remaining iterations, set n = n / 3, now apply steps 1, 2 and 3

Mohamed ennahdi el idrissi · Answer 3 · 2015-06-30T12:33:05+0000

Methodically, using Sigma notation, you can do the following:

enter image description here

0