A friend asked me this question ... Also asked me another modification ,
T(n) = T[ *mod*(n-2^( ceil(log n) )) ] +O(n) Can we find the complexity for such a recurrence ? On Mon, Sep 15, 2008 at 9:17 AM, Ashesh <[EMAIL PROTECTED]> wrote: > > You should agree with the fact that log(n-1) <= ceil(log(n-1)) < > log(n-1)+1, > which would mean that n-1 <= 2^(ceil(log(n-1))) < 2(n-1), thus, 2-n < > n-2^ceil(log(n-1)) <= 1. Thus, unless 2-n<1, there are no such > possible values. We must therefore have that n>1. > > Moreover, as long as the base of the logarithm is less than or equal > to 2, n-2^ceil(log(n)) <=0, and the second case shall hold. > > Where did you get this question from, if I may ask? > > On Sep 14, 10:00 pm, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote: > > 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 > > > -- 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
