Hello all,
I have a recurrence relation of the form
T(n) = T(n-2^log n) + O(n) ------- how do i solve such a recurrence
relation ?
I have tried an approach for this. Is this right ? -------
let kn = n-2^log n hence k ranges from 0 < k < [(2^log n -
2^log(n-1))/2n]
ie 0 < k < [2^(log n - 2)]/n
therefore,
T(n) = T(nk) + O(n)
= T((n-1)k) + O(nk) + O(n)
= T((n-2)k) + O((n-1)k) + O(nk) + O(n)
.
.
.
= T((n-i)k) + O[ k(n+(n-1)+....+(n-i+1)) +n ]
simplifying this we get,
T(n) = T((n-i)k) + O[ k(i-1)(i-2n)/2] + n ]
if i = n-1/k we get,
T(n) = T(1) + O{ (1/k)[(nk-1-k)(nk-1-2nk)/2 ] + n }
simplifying this we get,
T(n) = O(k*n^2)
substituting value of k we get,
T(n) varies from O(1) to O( n*2^(log n -2) ) as k varies form 0 to
[2^(log n - 2)]/n
Is this a right approach or am i missing something ?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
