Note: This answer is copied directly from Quora, here’s the link:- https://www.quora.com/How-do-you-solve-T-n-T-n-2-2-n-through-the-master-theorem
I am going to assume a base case when T(1) occurs, where it is some constant. You can indeed use the Master Theorem here (I am referring to the one in CLRS). As this is a great example for me to hand-wave as an exercise, I will not provide a full solution here; only the end-result and a tip on how to get it.
I am going to assume the following form when using the Master Theorem:
T(n)=aT(n/b)+f(n), where a≥1 and b>1 are constants and f(n) is an asymptotically positive function.
You can use the following case of the Master Theorem…
In short, you’re going to end up with $T(n)∈Θ(2^n).$
Aside: Instead, I’m going to show you another way to do this, without the Master Theorem. For simplicity, I am going to assume that nn is a power of 2 (you do not need to do this). I’m just going to use repeated substitution.
$ T(n)=T(n/2)+2^n$
$=(T(n/4)+2^{n/2})+2^n$
$=(T(n/8)+2^{n/4})+2^{n/2}+2^n$
$=(T(n/16)+2^{n/8})+2^{n/4}+2^{n/2}+2n$
Well if you are observant, you will notice if we continue this, I can just put in powers of two in above. Then…
$T(n)=T(n/2^i)+2^{n/2^{i-1}}+2^{n/2^{i-1}}+ ...+2^{n/2^{1}}+2^{n/2^{0}}.$
Well, we need when $n/2^i=1$, so just re-arrange this and apply logarithms to both sides and we obtain that
$i=\log_{2}n $
I am going to assume we keep substituting until we get T(1), then use a simple bound (that is a finite geometric series) that will consist of at least the terms of the sum.
=T(1)+$\sum_{j=0}^{i} 2^{n/2^j}$
<T(1)+$\sum_{j=0}^{i} 2^{j}$
=T(1)+$2^{n+1}−1$ (Applying the fact it is a finite geometric series with r=2)
=T(1)+$2(2^n)−1$
Well, we said T(1) is constant, so T(1)−1 must also be constant.
We can see that $2(2^n)∈Θ(2^n), therefore, T(n)∈Θ(2^n).$
