divide and conquer recurrence iteration

Question

I am currently studying Divide and conquer.

I have been reading algorithm design by Jon Kleinberg along with the lecture slides from our lecturer.

I am stuck with the part where they teach us about the solution of divide and conquer recurrences.

I could not understand how they got the answer.

It goes like this.

Fix $a > 0$, $b > 1$ and consider

$T(n) = aT(\frac{n}{b}) + f(n)$ (when $ n > n_{0}),$ $ n_{0} = c.$

First solve this when $\frac{n}{n_{0}}$ is a power of b:

put $U(i) = T(n_{0}b^i)$ and $ g(i) = f(n_{0}b^i).$

Get

$U(i) = aU(i - 1) + g(i)$ (when $i > 0$), $U(0) = c)$

iterate to obtain

Important special case: $f(n) = n^p$ for some fixed $p$.

Write $B = b^p$.

What I do not understand is that when they said "when $\frac{n}{n_{0}}$ is a power of b:", $n$ should be something like $n = n_{0}b^i$. After that when we substitute $T(n)$ with the $n = n_{0}b^i$, it should be something like

$T(\frac{n_{0}b^i}{b})$

How did they end up with $T(n_{0}b^i)$?

Also they said iterate to obtain

How did they obtain that? They did not provide any walk through that I could follow on how to get that..

Do I need to use induction? or any other methods?

Thank you.

Answer 1

If $f(n)$ is monotone increasing (normally a given in divide-and-conquer cases), it is clear that $T(n)$ is also monotone increasing. If we just consider $n = n_0 b^k$, the values will interpolate and for asymptotic behaviour we are clear. Define $t_k = T(n_0 b^k)$, so that $k = \log_b n$, and you can write the recurrence as:

$\begin{align} t_k = a t_{k - 1} + f(n_0 b^k) \end{align}$

To solve this, divide by $a^k$ to get:

$\begin{align} \frac{t_k}{a^k} - \frac{t_{k - 1}}{a^{k - 1}} &= \frac{f(n_0 b^k)}{a^k} \\ \frac{t_k}{a_k} - t_1 &= \sum_{2 \le j \le k} \frac{f(n_0 b^j)}{a^j} \\ t_k &= a^k t_1 + a^k \sum_{2 \le j \le k} \frac{f(n_0 b^j)}{a^j} \\ T(n) &= a^{\log_b n} T(n_0 b) + a^{\log_b n} \sum_{2 \le j \le \log_b n} \frac{f(n_0 b^j)}{a^j} \\ &= n^{\log_b a} T(n_0 b) + n^{\log_b a} \sum_{2 \le j \le \log_b n} \frac{f(n_0 b^j)}{a^j} \end{align}$

Here we used:

$\begin{align} a^{\log_b n} &= b^{\log_b a \cdot \log_b n} = \left( b^{\log_b n} \right)^{\log_b a} = n^{\log_b a} \end{align}$

How this behaves as $n \to \infty$ now depends on the two terms on the right.