How to solve the recurrence function T (n) = 2T (n ^ 1/2) + logn? Book Exercise Cormen cap 4 [closed]

3

In the book of Cormen, Cap 4 details how to solve func- tions of recorrecia (Cap 4). One of the exercises asks to solve. I tried using the tree and the induction but I could not move. How to reduce the log n and n ^ 1/2 values so that you can check the Big-O function?

    
asked by anonymous 11.04.2016 / 15:46

1 answer

2

Since log (n) is in base 2, the solution of the recurrence function looks like this:

T(n) = 2*T( sqrt(n) ) + log(n)

Substituindo n = 2^m  
T(2^m) = 2*T( sqrt(2^m) ) + log(2^m)  
T(2^m) = 2*T( 2^(m/2) ) + m

Considering the following transformation:

S(m) = T(2^m)  
Temos:  
S(m) = 2*S(m/2) + m

We can replace m = 2 ^ x

S(2^x) = 2*S( 2^(x-1) ) + 2^x

And we can be substituting recursively

S( 2^(x-1) ) = 2*S( 2^(x-2) ) + 2^(x-1)  
S( 2^(x-2) ) = 2*S( 2^(x-3) ) + 2^(x-2)  
S( 2^(x-3) ) = 2*S( 2^(x-4) ) + 2^(x-3)  
...

Getting:

S(2^x) = 2*[2*[2*[...] + 2^(n-2)] + 2^(n-1)] + 2^n

Doing until S (1) and solving the summation we have:

S(2^x) = 2^x*S(1) + x*2^x  
Como S(1) = 1  
S(2^x) = 2^x + x*2^x

Substituting n = 2 ^ x

S(n) = n + log(n)*n

This is the solution of the S(n) = 2*S(n/2) + n recurrence function that is isomorphic to the function we want by the S(n)=T(2^n)

So replacing

S(m) = T(2^m)  
T(2^m) = S(m) = m + log(m)*m

And finally replacing n = 2 ^ m we have:

m = log(n)

T(n) = log(n) + log( log(n) )*log(n)

This is the solution of the given recurrence function and therefore it has the following complexity:

O(T(n)) = log(n) * log( log(n) )
    
18.04.2016 / 15:08