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