0
$\begingroup$

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

enter image description here

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

enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ $n/n_0$ power of $b$ means that $n=n_0b^k$ so $\frac{n}{b}=n_0{b}^{k-1}$ and if we put $i=k-1$ you get their form. They said that $\frac{n}{n_0}$ was a power of $b$ so it could be any number they didnt specify that. Think of it as a mute variable like what happens in constant of integration. $\endgroup$ – Oussama Boussif Sep 6 '15 at 14:15
  • 1
    $\begingroup$ That makes much more sense now. Thank you very much :D $\endgroup$ – Andy Min Sep 6 '15 at 14:36
  • $\begingroup$ Glad I helped @Andy Min . For the recurrence relation just try for variuous values of $i$ and then you'll observe the pattern and try proving it using induction. $\endgroup$ – Oussama Boussif Sep 6 '15 at 14:39
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.