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

Question

If not, witch complexity it would be? Thanks:

    public static int f(int n, int x) {
        for (int i = n; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                x += j; // Assume, this operation costs 1.
            }
        }
        return x;
    }

Answer 1

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).