# How do I solve this recurrence equation?

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.

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}

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.

• Another hint : You should verify your solution by using substitution Feb 20 at 12:58

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.