Has this snippet O(log^2(n)) complexity?

This is an interesting one. The assumption of log^2(n) is wrong. Henry gave a good reductio ad absurdum why it cannot be log^2(n) in the comments:

• We can see that, O(log^2(n)) ⊊ O(n).
• the first iteration of the inner loop takes O(n).
• Since O(log^2(n)) ⊊ O(n), the assumption must be wrong because the first iteration alone is ∈ O(n).

This also provides us with a lower bound for the algorithm: Since the first iteration of the algorithm is ∈ O(n), then whole algorithm takes at least Ω(n).

Now let us get to estimating the execution time. Normally, the first approach is to estimate the inner and outer loop separately and multiplying them together. Clearly, the outer loop has complexity log(n). Estimating the inner loop, however, is not trivial. So we can estimate it with n (which is an overestimation) and get a result of n log(n). This is an upper bound.

To get a more precise estimation, let us make two observations:

1. The inner loop basically adds up all values of outer loop variable i
2. Loop variable i follows the pattern of n, n/2, n/4, ..., 1, 0

Let us assume that n = 2^k, k ∈ ℕ, k > 0, i.e. n is a power of 2. Then n/2 = 2^(k-1), n/4 = 2^(k-2), ... To generalize from this assumtion, if n is not a power of 2, we set it to the next smaller power of 2. This is, in fact, an exact estimation. I leave the reasoning as to why as an exercise for the reader.

It is a well-known fact that 2^k + 2^(k-1) + 2^(k-2) + ... + 1 (+ 0) =sum_(i=0)^k 2^i = 2^(k+1) - 1. Since our input is n = 2^k, we know that 2^(k+1)= 2 * 2^k = 2 * n ∈ O(n). The algorithm's runtime complexity is, in fact, Θ(n), i.e. this is an upper and a lower bound. It is also a lower bound since the estimation we made is exact. Alternatively, we can use our observation of the Algorithm being ∈ Ω(n) and thus arrive this way at Θ(n).

First of all, look at the outer loop. You can see it iterates until i < 1 or i = 0. So, outer loop executes for values for i = N, N/2, N/4 … N/2^k (executing k number of times)

N/2^k < 1

N<2^k

k>log(N)

so, outer loop executes logN times.

Now, looking at inner loop. First of all, it executes for N times, then N/2 times then N/4 times until it reaches 1. Basically, executing logN times.

So, time complexity will be N + N/2 + … logN terms.

By Geometric progression: a=N, r= 1/2, n= logn (Remember logn has base 2) Also, using a^logb = b^loga and log2 is 1.

N((1- (1/2)^logN)/(1-1/2)) = 2N(1-(1^logN)/(N^log2)) = 2N(1-1/N)=2(N-1) = 2*N = O(N)

So, time complexity is O(N)

Linear O(n)

Total cost = n (first outer loop iteration) + n/2 (second outer loop iteration) + n/4 (third) + ... etc to a total of log(n) iterations. This sum is bounded by 2n (sum of a geometric series with a = n, r = 1/2).