Menu
Master Method is a direct way to get the solution. The master method works only for the following type of recurrences or for recurrences that can be transformed into the following type. There are the following three cases: If f(n) = O(nc) where c < Logba then T(n) = Θ(nLogba)
A recurrence or recurrence relation defines an infinite sequence by describing how to calculate the n-th element of the sequence given the values of smaller elements, as in: T(n) = T(n/2) + n, T(0) = T(1) = 1.
The recurrence (4.5) describes the running time of an algorithm that divides a problem of size n into a subproblems, each of size n/b, where a and b are positive constants. The a subproblems are solved recursively, each in time T(n/b).
Am trying to solve the given recursion, using recursion tree, T(n) = 3T(n/3) + n/lg n.
In the first level (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).
In the second level it turns out to be n/(log(n/9)).
Can I generalize the above equation in the form of n.loglogn
This is a general doubt I've, I need an insight on this.
Note:
Any function that has to be Theta(n^k log^k (n)) in that function k should >=1. And in this case k is -1 so master theorem doesn't come in to picture
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With