# Not sure if my solution to following recurrence is correct

I have a recurrence relation, it is like the following:

$T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm.

To solve this and find a $\Theta$ bound, I tried the following: I put $k=e^n$, and the equation transforms into:

$$T(k)=2T(k/e)+k$$

Then, I try to use the Master Theorem. According to Master Theorem, $a=2$, $b=e\gt 2$ and $f(k)=k$. So, we have the case where $f(k)=\Omega(n^{\log_b a+ε})$ for some $ε\gt 0$, thus we have $T(k)=\Theta(f(k))=\Theta(k)$. Then put $k=n$, we have $T(n)=\Theta(n)$. Does my solution have any mistakes?

• See this relevant meta post. You should probably make your question relevant to others.
– Raphael
Mar 7 '13 at 12:01

$c=1\gt \ln 2\approx0.7$. That's case 3 of the master theorem. It follows that:

$$T(n)=\Theta(n)$$

Just use the change of variables $$t(n) = T(e^n)$$, you get $$t(n) = t(n - 1) + e^n$$. Linear, first order recurrence, solution is:
$$\begin{equation*} t(n) = t(n - 1) + e^n \end{equation*}$$
\begin{align*} t(n) &= t_0 - \frac{e}{e - 1} + \frac{e^{n + 1}}{e - 1} \\ T(k) &= (t_0 - \frac{e}{e - 1}) + \frac{e^2}{e - 1} k \\ &\sim \frac{e^2}{e - 1} k \end{align*}