Actually there is one more condition to it but i thought it will be more
complicated
to mention it,
at each step we subtract 2^(ceil(log n) if n-2^( ceil(log n) ) > 0
else we subtract n-2^( ceil(log (n-1)) )
So,
T(n) = T[ n-2^( ceil(log n) ) ] +O(n) for n-2^( ceil(log n) )>0
= T[ n-2^( ceil(log (n-1)) ) ] + O(n) for n-2^( ceil(log n) )<0
On Sun, Sep 14, 2008 at 9:51 AM, Ashesh <[EMAIL PROTECTED]> wrote:
>
> In such a case, ceil(log(n)) > log(n), and if the base of the
> logarithm is 2 or less, then 2^(ceil(log(n)) > n, and the question
> fails to be valid. The base of the logarithm has to be greater than 2.
>
> On Sep 14, 9:26 pm, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote:
> > Sorry i forgot, it is ceil(log n) so n-2^( ceil(log n) ) is not equal to
> > zero..
> >
> > On Sun, Sep 14, 2008 at 8:57 AM, Karthik Singaram Lakshmanan <
> >
> > [EMAIL PROTECTED]> wrote:
> >
> > > Isn't n-2^logn = 0?
> > > since 2^logn = n if you are talking about log base 2
> >
> > --
> > Ciao,
> > Ajinkya
> >
>
--
Ciao,
Ajinkya
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
