0
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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}

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Another hint : You should verify your solution by using substitution $\endgroup$ Feb 20, 2023 at 12:58
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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