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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---