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.