Understanding the Master Theorem - Determining the levels of recursion

Question

I am trying to understand the proof for the Master Theorem. I have started by unwinding the following recurrence in order to find the total running time of an algorithm whose time complexity can be modelled by the following recurrence:

$$ T(n) = aT(n/b) + f(n) $$

where $a$ and $b$ are both integers, $a >= 1, b > 1$ and $f(n) > 0$

I understand that at level 'j' of the recursion, the number of subproblems is $a^j$, with each subproblem having a size of $n/b^j$, and each subproblem taking time at most $f(n/b^j)$. Therefore, level 'j' contributes a total of at most $a^j*f(n/b^j)$ to the total running time.

I have read that there are $\log_bn$ levels of recursion for an algorithm that follows the above recurrence. However, I don't understand how the number of levels of recursion is derived to be $\log_bn$. Any insights are appreciated.

Answer 1

The level of recursions should rather be

• $\lceil \log_b n \rceil$

You can see this quite easily if you consider the special cases $n=b^m$:

• $n = b^1 \Rightarrow 1$ recursion $\Rightarrow 1 = \log_b b$.

Obviously you need also for $1\leq n < b$ at least $1$ round. So, the level of recursions here is $\lceil \log_b n \rceil$.

Similarly:

• $n = b^m \Rightarrow m$ recursions $\Rightarrow m = \log_b n$

For $b^{m-1} +1 \leq n < b^m$ you also have $m = \lceil \log_b n \rceil$ recursions, because after $m-1$ recursions there are still $b \geq n-b^{m-1}>0$ tasks left to be solved.