time complexity for this algorithm

Question

for (i = 1; i <= n; i *= 2)
    for (j = 1; j <= i; j++)
        sum++;

I think it's time complexity is O(n) (1 + 2 + 2 + 3 + 3 + 3 ... = (1(2^(log2n)-1))/(2-1), sum of geometric sequence). Is it right? I'm confused with my answser.

log(n) * (log(n) + 1) / 2 according to WolframAlpha... Which is basically O(log(n) ^ 2). — goodvibration
– goodvibration, Commented Oct 18, 2020 at 9:12
i grows by being *2 at each iteration, thus the number of iterations will be much smaller than n, log2(n) actually. Then the j loop will do 1, then 2... or 1+2+...+log2(n) iterations, meaning O(log2(n)^2) = O(log(n)^2). — Déjà vu
– Déjà vu, Commented Oct 18, 2020 at 9:13

OmG · Accepted Answer · 2020-10-18 10:31:15Z

3

i changes in these steps: 1, 2, 2^2, ..., 2^log(n) and in each iteration of the outer loop, the inner loop run i times. Hence, the time complexity T(n) is 1 + 2 + 2^2 + ... + 2^log(n) which is equal to 2^{log(n) + 1} -1. Threfore, T(n) = Theta(n).

answered Oct 18, 2020 at 10:31

OmG

19k13 gold badges69 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

time complexity for this algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related