I want to solve the recurrence relation: T(n)=2T(sqrt(n))+1, without using the Master Theorem.

That's what I have tried:

m=lg(n) => 2^m=n => 2^(m/2)=sqrt(n)

So we have: T(2^m)=2T(2^(m/2))+1

We set S(m)=T(2^m) and we have: S(m)=2S(m/2)+1

We will show that S(m)=Θ(m), i.e. that there are c_1', c_2'>0, n_0 ∈ N_0 such that forall m>= n_0: c_1' m <= S(m) <= c_2' m

We suppose that there are c_1, c_2>0, n_1 ∈ N_0 such that c_1 k <=S(k) <= c_2 k, for all n_0<=k<m


We will show that c_1 m <= S(m) <= c_2 m