I have to express the solution of the recurrence equation T(n) = T(an) + n where a is a constant, 0 < a < 1, in terms of θ using the iteration method. I am unsure of how I calculate the cost of each level and the number of levels because of the constant a.
3 Answers
$\begingroup$
$\endgroup$
To resolve $$T(n)=T(\tilde{a}n)+n$$
you can apply the Master Theorem(https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)):
the recurrence: \begin{equation} T(n) = \begin{cases} a T(n / b) + f(n) & n > 1 \\ T_1 & n = 1 \end{cases} \end{equation} with constants $a \geq 1$, (b > 1), the function (f(n) > 0), with constants $ \alpha = \log_b a $ has the solution:: \begin{equation*} T(n) = \begin{cases} \Theta(n^{\alpha}) & \text{\(f(n) = O(n^c)\) para \(c < \alpha\)} \\ \Theta(n^{\alpha}) & \text{\(f(n) = \Theta(n^{\alpha} \log^\beta n)\) con \(\beta < -1\)} \\ \Theta(n^{\alpha} \log \log n) & \text{\(f(n) = \Theta(n^{\alpha} \log^\beta n)\) con \(\beta = -1\)} \\ \Theta(n^{\alpha} \log^{\beta + 1} n) & \text{\(f(n) = \Theta(n^{\alpha} \log^\beta n)\) with \(\beta > -1\)} \\ \Theta(f(n)) & \text{\(f(n) = \Omega(n^c)\) with \(c > \alpha\) y \(a f(n / b) < k f(n)\)}\\ &\text{for \(n\) large with \(k < 1\)} \end{cases} \end{equation*} in our case: $a=1$, $b=\frac{1}{\tilde{a}}$ and $f(n)=n$ $\Rightarrow \alpha=0$
so \begin{aligned} T(n)&=\Theta(f(n))\\ &=\Theta(n)\\ \end{aligned} otherwise, as it says Yves Daoust:
\begin{aligned} T(n)&=T(\tilde{a}n)+n\\ &=(T(\tilde{a}^2n)+\tilde{a}n)+n\\ &=((T(\tilde{a}^3n)+\tilde{a}^2n)+\tilde{a}n+n)\\ &\vdots\\ &\text{notice that we have a polynomial of n}\\ &=T(\tilde{a}^m n)+ \Theta(n)\\ \end{aligned} where, for finite m (when does the recursion stop?) $$T(n)=\Theta(n)$$ I suppose that for that m $T(\tilde{a}^m\cdot n)$ it has a constant cost (the base case, as Yves says).
The base case is important when defining recurrence!
to do it exactly you must calculate the sum of the m terms:
\begin{aligned} T(n)&=((T(\tilde{a}^3n)+\tilde{a}^2n)+\tilde{a}n+n)\\ &=T(\tilde{a}^m n)+ n\sum_{i=0}^{m-1}(\tilde{a}^i)\\ &=T(\tilde{a}^m n)+n\frac{1-\tilde{a}^m}{1-\tilde{a}}\\ \end{aligned}
$\begingroup$
$\endgroup$
1
Hint:
$$T(n)=T(an)+n=T(a^2n)+an+n=T(a^3n)+a^2n+an+n=\cdots$$
You can stop the expansion when $a^kn=1$ and use the geometric sum formula.
-
$\begingroup$ Another hint : You should verify your solution by using substitution $\endgroup$ Feb 20 at 12:58
$\begingroup$
$\endgroup$
Hint.
Making $n = a^m$ we have
$$ T(a^m) = T(a^{m+1})+a^m $$
or recasting
$$ R(m+1) = R(m) - a^m $$
etc.
