algorithm - order of growth for loop worst case running time

Question

I am having trouble with this. The inner loop depends on the outer loop and from trying out values of n, the loop runs 1+2+4...+sqrt(n) times. Any help would be greatly appreciated!

int sum = 0;
for (int k = 1; k*k <= n; k = k*2)
    for (int j = 0; j < k; j++)
        sum++;

question from:https://stackoverflow.com/questions/66059293/order-of-growth-for-loop-worst-case-running-time

Answer 1

If K is the largest power of 2 with K*K <= n, then your sum is 1+2+4+8+...+K = 2K+1.

K is clearly less than or equal to sqrt(n), but it's also greater than sqrt(n)/4 (because if not, then 2K*2K would be less than or equal to n, contradicting the fact that K is the largest power of 2 with K*K <= n.

So sqrt(n)/4 < K <= sqrt(n), and your runtime (2K+1) is between sqrt(n)/2+1 and 2sqrt(n)+1, and thus the complexity is Θ(sqrt(n)).