What is time complexity for this function?

Question

Consider this function:

void func()
{
    int n;
    std::cin >> n;
    int var = 0;

    for (int i = n; i > 0; i--)
        for (int j = 1; j < n; j *= 2)
            for (int k = 0; k < j; k++)
                var++;
}

I think that the time complexity is O(n^2 * log n) but when n is 2^m, I have a hard time thinking what complexity it is.

How can I analyze the complexity of this function?

Answer 1

n isn't a constant, it's dynamic, so that's the variable in your analysis. If it was constant, your complexity would be O(1) regardless of its value because all constants are discarded in complexity analysis.

Similarly, "n is 2^m" is sort of nonsensical because m isn't a variable in the code, so I'm not sure how to analyze that. Complexity analysis is done relative to the size of the input; you don't have to introduce any more variables.

Let's break down the loops, then multiply them together:

for (int i = n; i > 0; i--) // O(n)
    for (int j = 1; j < n; j *= 2) // O(log(n))
        for (int k = 0; k < j; k++) // O(n / log(n))

Total time complexity: O(n * log(n) * (n / log(n))) => O(n^2).

The first two loops are trivial (if the second one isn't obvious, it's logarithmic because of repeated multiplication by 2, the sequence is 1, 2, 4, 8, 16...).

The third loop is tougher to analyze because it runs on j, not n. We can simplify matters by disregarding the outermost loop completely, analyzing the inner loops, then multiplying whatever complexity we get for the two inner loops by the outermost loop's O(n).

The trick is to look at the shape of the enclosing loop; as the j loop approaches n, k is running from 0..n linearly, giving a baseline of O(n) for the k loop. This is scaled by a logarithmic factor j, O(log(n)). The logarithmic factors cancel and we're left with O(n) for the inner loops.

Here's some empirical evidence of the inner loop complexity:

import math
from matplotlib import pyplot

def f(N):
    count = 0
    j = 1
    while j < N:
        j *= 2
        count += j
    return count

def linear(N):
    return N

def linearithmic(N):
    return N * math.log2(N) if N else 0

def plot_fn(fn, n_start, n_end, n_step):
    x = []
    y = []

    for N in range(n_start, n_end, n_step):
        x.append(N)
        y.append(fn(N))

    pyplot.plot(x, y, "-", label=fn.__name__)

def main():
    max_n = 10 ** 10
    step = 10 ** 5

    for fn in [f, linear, linearithmic]:
        plot_fn(fn, 0, max_n, step)

    pyplot.legend()
    pyplot.show()

if __name__ == "__main__":
    main()

The plot this produces is:

This shows that the innermost two loops (in blue) are linear, not linearithmic, confirming the overall quadratic complexity once the outermost linear loop is re-introduced.