An "accessible" solution to a deceptively hard complexity analysis question

Consider the following recursive algorithm:

def f(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return g(n) + f(n / 2) + f(n / 2)

Given that g(n) has time complexity $O(\log{n})$, we want to determine the time complexity of f(n). Let's see if we can work out the answer without using any powerful machinery one might initially be tempted to use.¹ Most of the difficulty will actually be in evaluating sums, but this should be doable if you've done MATH1081.

In all that follows, we will make some simplifying assumptions:

Assume that $n$ is a power of 2. This is OK, because otherwise we can replace it by $2^{\lceil \log_2{n} \rceil} \geq n$ instead and still obtain a suitable upper bound on the complexity of f(n).
Assume that $n$ is big enough that an upper bound on the amount of work g(n) does is $C\log(n)$ for some constant $C$, and that this is implicitly the logarithm of base 2. This is also OK, because g(n) has time complexity $O(\log{n})$, so this is just a formal interpretation of what this big-O statement means. Also, by change of base, all logarithms are asymptotically equivalent, regardless of base, so we can just consider base 2.

Let's look at the call tree generated by f, i.e. a diagrammatic representation of how one call initiates further calls:

              f(n)                   | Level 0
            /      \
           /        \
          /          \
         /            \
        /              \
     f(n/2)          f(n/2)          | Level 1
    /      \        /      \
   /        \      /        \
 f(n/4)   f(n/4) f(n/4)   f(n/4)     | Level 2
  ...       ...    ...      ...      | Levels 3 .. log(n)

This tree has exactly $\log_2{n}$ levels, because when we halve $n$ this many times, we get a result of 1, at which point the base case stops any further calls. Also, on the $k$-th level, there are $2^k$ calls of f with the input $n/2^k$, and each causes a call to g with the same input. This suggests that the total amount of work done on this level is bounded above by $$2^k\left(1 + C \log\left(\frac{n}{2^k}\right)\right) + O(1) = 2^k\left(1 + C(\log{n} - k)\right) + O(1).$$

So, the total amount of work done over the whole tree is bounded above by $$\sum_{k = 0}^{\log{n}} 2^k (1 + C(\log{n} - k)) + O(1),$$ which, after a bit of grouping, splits into the three individual scaled sums $$\sum_{k = 0}^{\log{n}} O(1) + (1 + C\log{n}) \sum_{k = 0}^{\log{n}} 2^k - C \sum_{k = 0}^{\log{n}} k 2^k.$$

The first sum is obviously $O(\log{n})$. The second sum is a geometric progression, and is $$\sum_{k = 0}^{\log{n}} 2^k = 2^{\log{n} + 1} - 1 = 2n - 1.$$ For the last sum, after realising $1 = 2 - 1$, we can do a bit of trick reindexing to obtain $$\sum_{k = 0}^{\log{n}} k 2^k = \sum_{k = 1}^{\log{n}} (2 - 1) k 2^k = \sum_{k = 1}^{\log{n}} k 2^{k + 1} - \sum_{k = 0}^{\log{n} - 1} (k + 1) 2^{k + 1} = \sum_{k = 1}^{\log{n}} k 2^{k + 1} - \sum_{k = 0}^{\log{n} - 1} k2^k - \sum_{k = 0}^{\log{n} - 1} 2^{k + 1}.$$ After cancellation and more reindexing, the geometric progression from before appears again: $$\sum_{k = 0}^{\log{n}} k 2^k = 2^{\log{n} + 1} \log{n} + 1 - \sum_{k = 0}^{\log{n}} 2^k = 2n \log{n} + 1 - (2^{\log{n} + 1} - 1) = 2n \log{n} - 2n + 2.$$ Putting this all together then, we have that the total amount of work done is $$O(\log{n}) + (1 + C\log{n})(2n - 1) - C(2n\log{n} - 2n + 2) = O(n) + O(\log{n}) = O(n).$$

This answer intuitively suggests that the number of recursive calls was the dominating factor in f's complexity, not the work it did in each call. Sure enough, this is exactly what certain powerful machinery suggests should happen. This isn't a priori obvious just by looking at the code though!

Well, what we're about to do is, more or less, work through a specific case of a specific case of this powerful machinery. ↩

jedavidson/proof.md

Footnotes