Is my substitution solution to this recurrence correct?

Question

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

T(eⁿ) = 2(T(e^n-1)) + eⁿ, 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)=2T(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)=Ω(n^log_ba+ε) for some ε>0, thus we have T(k)=Θ(f(k))=Θ(k). Then put k=n, we have T(n)=Θ(n). Does my solution have any mistakes?

Answer 1

Let's work through this one step at a time.

You have the recurrence

T(eⁿ) = 2 T(e^n-1) + eⁿ

Now, let's do a variable substitution. Define k = eⁿ. Then we get

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

In this case, using the Master Theorem, we get that a = 2, b = e, and f(k) = k. Since logb a = ln 2 < 1 and f(k) = Θ(k), according to the Master Theorem the recurrence solves to S(k) = Θ(k).

If we now set k = n', where n' is the actual input to the function, then we get that T(n') = Θ(n), and we're done. So yes, the math checks out.

Hope this helps!