algorithm - Complexity of a nested geometric sequence -

below code bounded o(n^2), please explain why?

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

it's not tricky.

your inner loop's complexity forms geometric progression total omplexity o(n).

without filling details way (this seems hw problem), note formula geometric sequence is

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

and q^k here o(n).

your outer loop o(n).

since it's nested loop, , inner term not depend on outer index, can multiply.

Macro