What is the runtime for this code

Question

def mystery11(n):
  if n < 1: return n
  def mystery12(n):
    i = 1
    while i < n:
      i *= 2
    return i
  return mystery11(n/2) + mystery11(n/2) + mystery12(n-2)

I have a question about the code above. I completely understand that without the last recursive call to mystery12, the runtime of the code (mystery11) would be theta(n). But I don't believe that at each level theta(log(n)) work is being done.

At the first level, we do log(n), at the next level, we do 2log(n/2), then 4log(n/4)... but that doesn't look like log(n) at each level (it feels closer to 2log(n) at the second level and 4log(n) at the third level etc.)

I've also tried Wolfram Alpha, and I just get no solutions exist. But works fine without the log(n) term.

So, is this solution correct theta(nlog(n))? And if not, what is the actual solution?

Ps. Apologies if anything in my post is not etiquette, this is my second time posting on Stackoverflow. Post a comment and I will fix it.

Answer 1

Since mystery12 is independent of any external functions / variables, let's look at it first.

After the j-th iteration of the while-loop, i = 2^j. Therefore the maximum number of loops is given by the equation 2^j >= n, or j = ceil(log2(n)) where ceil rounds up to the nearest integer.

---

Now for mystery11. Each call contains 2 recursive calls to mystery11 with argument n / 2, and a call to mystery12 with argument n - 2. This gives the time complexity recurrence relation (C is some positive constant):

You have already correctly deduced that the recursion depth is m ~ log n. The precise value is m = ceil(log2(n)). Using the fact that a number rounded up only differs from itself by less than 1, we can eliminate some of the rounding brackets:

---

Let's examine B first. A problem arises - the expression inside the logarithm can be negative. This is mitigated by the fact that the while-loop mystery12 never executes if n - 2 < 1 - i.e. its complexity can be truncated to O(1) in this edge case. Therefore, the sum is bounded from above by:

Where we used a Taylor expansion of log. Hence B can be ignored in our analysis as it is already overshadowed by the first term.

---

Now to examine A. This is a slightly tedious summation which I will use Wolfram Alpha to compute:

Therefore the overal time complexity of mystery11 is Θ(n), not Θ(n log n) as predicted.

---

Why is this? The reason lies in "each recursive call does log n work" - n here is not the same as the initial value of n passed to mystery11 (the n in the overall time complexity). At each recursion level n decreases exponentially, so:

We cannot naively multiply the amount of work done per call with the number of recursive calls.

This applies to complexity analysis in general.