Solving the following recurrence relation

Question

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

$$ T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm} $$

To solve this and find a Θ bound, i tried the following: I put k=eⁿ, and the equation transforms into: $$ T(k)=2\cdot T(k/e)+k $$ Then, i try to use the master theorem. According to master theorem, $a=2, b=e>2 $ and $f(k)=k$. So, we have the case where $f(k)=\Omega(n^{log_a b + \epsilon})$ for some $\epsilon$>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?Thanks

Answer 1

Looks fine to me. Even better, you can plug $T(k)=2T(k/e)+k$ directly in Wolfram Alpha to get an exact answer.