NESTED_CMPL3

What is time complexity of following code :

        int count = 0;
        for (int i = N; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                count += 1;
            }
        }

•  O(N * N)
•  O(N * log N)
•  O(N * log(log(N)))
•  O(N)
•  O(N * Sqrt(N))

Good Solution:

It’s not that the complexity of the outer loop isn’t considered, its that it has to be considered in relation to the inner loop, because the inner loop is dependent upon the outer loop.

Unfortunately, especially regarding interviews, software engineers who are either rusty at math, or don’t have math backgrounds, get use to solving these kinds of problems by simply eyeballing it. Saying to themselves “well that outer loop is O(log n) and the inner loop is O(n), so the solution must be O(n log n).” That would only be true, if the inner loop wasn’t dependent upon the outer loop. In that case we could simply say O(n * log n), and call it day.

That’s not the case here, because the inner loop is only counting up to i. What this means is, because the inner loop is dependent upon the outer loop, we must then “count” how many times the inner loop actually gets executed.

So for the first iteration, the inner loop is executed N times, the second iteration N/2 times, then N/4 times. So we end up having to write the following equation:

T(N) = N + N/2 + N/4 + N/8 +

This turns into to

T(N) = N( 1 + 1/2 + 1/4 + 1/8 + 1/16…)

At this point, its up to the reader to understand that this is a geometric sequence. And unfortunately, if interview bit is going to give these kinds of problems, then they should include a unit on calculating the sums of Geometric sequences. A geometric sequence is defined as a sequence of numbers in which the ration between consecutive terms in constant. There are a bunch math proofs that can be read which explain why the geometric sequence above is upper bound by 2, as n approaches infinity.

Unfortunately, interview bit hasn’t provided or alluded to any of this material, which I frankly think is a mistake. There is no way to correctly solve this problem, given the inner loop is dependent upon the outer loop, without understanding how to sum geometric sequences.