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 -~----------~----~----~----~------~----~------~--~---
