Complexity of a nested geometric sequence

Question

Below code is actually bounded by O(n^2), could anyone please explain why?

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

Answer 1

It's not that tricky.

---

Your inner loop's complexity forms a geometric progression with total omplexity O(n).

Without filling the details all the way (this seems like a HW problem), note that the formula for a geometric sequence is

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

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

---

Your outer loop is O(n).

---

Since it's a nested loop, and the inner term does not depend on the outer index, you can multiply.

Answer 2

The proof is geometric progression :)

1. For i = n, the inner loop doesn't execute more than once if i > n/3 (because in next iteration j is >= n).

2. So for 2n/3 iterations of outer loop the inner loop iterates only once and does O(j) operation. So for 2n/3 iterations the complexity is O(n^2).

3. To calculate complexity of remaining iterations set n = n/3, now apply steps 1, 2 and 3

Answer 3

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