3
In Cormen’s book, Cap 4 details how to solve recurring functions (Cap 4). One of the exercises asks to solve. I tried using the tree and to induce but I could not go forward. How to reduce the values of log n and n 1/2 so that I can check the function Big-O?
2
Whereas log(n) is at base 2, the solution of the recurrence function is thus:
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 recursively replace
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
Making up to reach S(1) and solving the sum we have:
S(2^x) = 2^x*S(1) + x*2^x
Como S(1) = 1
S(2^x) = 2^x + x*2^x
Replacing n = 2 x
S(n) = n + log(n)*n
This is the solution of the recurrence function S(n) = 2*S(n/2) + n that is isomorphic to the function we want by transformation S(n)=T(2^n)
Therefore 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) )
S(1) = 1 was chosen as the initial value, which is equivalent to T(2)=1, but for any other value the reasoning is the same and the complexity also.
Browser other questions tagged c
You are not signed in. Login or sign up in order to post.
You can find a solution in MATH
– lsalamon