1

I'm trying to solve this recursive relation: $$\ T(n) = 2nT(\sqrt n)+1 $$

I tried to set $ m = 2^m $ but I'm stuck.

I got a Hint: Use recursive tree..

Anybody?... Thank!

Nir Avraham
  • 11

1 Answers1

1

Set $n=2^{2^m}$, so that $\sqrt n=2^{2^{m-1}}$.

Now we have an ordinary linear first order recurrence,

$$t_m=2^{2^m+1}t_{m-1}+1.$$

Then

$$t_1=8t_0+1,$$

$$t_2=32t_1+1=256t_0+33,$$

$$t_3=512t_2+1=131072t_0+16897,$$ $$\cdots$$

The coefficient in front of $t_0$ can be evaluated as

$$\prod_{j=1}^m2^{2^j+1}=2^{\sum_{j=1}^m2^j+1}=2^{2^{m+1}+m-2},$$ giving the homogeneous solution.

In terms of $n$, this is

$$2^{2^{m+1}+m-2}=2^{2^{\lg(\lg(n))+1}+\lg(\lg(n))-2}=\frac{n^2\lg(n)}4.$$

The case of the independent term seems harder to handle, but it "suffices" to find any solution of the non-homogeneous equation.