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