Don't know if the O-notation is also defined for complex functions. Well, if it isn't, here's a possibility: - (please correct me if I am wrong here.. )
For sqrt( x ) to be real, x needs to be > 0 => log(log(m)) / log(m) > 0 But we also know that log(m) > log(log(m)) for all values of m for which log(log(m)) is defined. => log(log(m)) / log(m) < 1 Also sqrt(x), for 0<x<1 is also in the interval (0, 1) => we have a bound on the O( sqrt(blah..blah.blah..) ) = O(1) Thus, the recurrence reduces to T(m) = T(m/2) + O(1) This happens to be a lot easier to solve.. Thanks, mayur On 6/12/07, Phanisekhar B V <[EMAIL PROTECTED]> wrote: > Hi Ray, > Can u do this without using Master theorem? > > I also need to fine the time complexity of problems like: > > T(m) = 2T(m/2) + O( m^2 * squareroot((log log m) / (log m)) ) > > basically i need a solution without using master theorem. > > Regards, > Phani > > > > On 6/12/07, Ray <[EMAIL PROTECTED]> wrote: > > > > I think it's O(n). > > > > Because the order of squareroot((log log m) / (log m)) is less than > > m's. > > > > T(n) = a T (n/b) + f(n) > > > > 1. O(n ^(lgb/lga) ) > O(f(n)) > > T(n) = O(n ^(lgb/lga)) > > > > 2. O(n ^(lgb/lga) ) = O(f(n)) > > T(n) = O(lg(n)*f(n)) > > > > 3. O(n ^(lgb/lga) ) < O(f(n)) > > T(n) = O(f(n)) > > > > The problem fits the 1st situation. So it's O(n). > > > > On Jun 12, 4:11 pm, "Phanisekhar B V" < [EMAIL PROTECTED]> wrote: > > > Adiran, Yes u r right. Let T(1) = 1. > > > > > > On 6/12/07, Adrian Godong <[EMAIL PROTECTED]> wrote: > > > > > > > > > > > > > > > > > > > You should provide the limit/point where T(m) is constant. > > > > > > > Say T(1) = 1, or something else. Only then we can calculate the time > > > > complexity. > > > > > > > On 6/12/07, Phanisekhar B V <[EMAIL PROTECTED]> wrote: > > > > > > > > How can i calculate the time complexity of the following problem? > > > > > T(m) = 2T(m/2) + O( squareroot((log log m) / (log m)) ) > > > > > > > > The above problem contains double log and squareroot. > > > > > > > > Regards, > > > > > Phani > > > > > > > > Microsoft MVP > > > > > < https://mvp.support.microsoft.com/profile/Adrian> > > > > >https://mvp.support.microsoft.com/profile/Adrian- > Hide quoted text - > > > > > > - Show quoted text - > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
