On Jul 21, 8:38 pm, zpedja <[EMAIL PROTECTED]> wrote:
> On Jul 21, 12:40 pm, Ashesh <[EMAIL PROTECTED]> wrote:
>
> > zpedja wrote:
> > > Hi, I need help for these two equations:
> > > 1)
> > > For the first one I need an asymptotic solution:
> > > T(1)=T(2)=1,
> > > T(n) = T( ceil( n/log(n) ) ) + 1 , n>=3
>
> > > I think it should be O(log(n)), but I don't know how to prove it.
>
> > I disagree. The recurrence will terminate when ceil(n/log(n)^k) <=3
> > because, from what you've mentioned in your problem, for the
> > recurrence to hold, we must have x>=3, if the recurrence be given by
> > T(x) (I'm using x to avoid confusion here).
>
> Yes, your solution might be more precise. I think that my solution as
> an upper bound would do, even though it's a bit coarse.
> I'm now dealing with your solution.
> I've managed to prove that the argument in k-th recursion acts like
> ceil(n/log(n)^k) , but I don't know how you obtain k=Θ( log(n)/
> log(log(n)) ).
Asymptotically speaking, the recurrence reaches an end when n/log(n)^k
= ϴ(1) = c, where c is a constant. So, c.log(n)^k = n
or, k.log(log(n)) + logc = log(n)
getting rid of the constant, the asymptotic expression for k would
then be: k=ϴ( log(n) / log(log(n)) ).
>
> > Asymptotically, we'll get k=Θ(log(n)/log(log(n)), and since the
> > asymptotic addition in the recurrence is Θ(1), we'll get T(n) =
> > Θ( log(n) / (log(log(n)) ) = ( lg(n) / lg(lg(n)) )
>
> I solved the second equation in a different way. Just divide the
> equation with 4^(k+1) and sum equations with index k going from 1 to
> floor(log_3(n)). Then you get something like:
> T(n)/4^(log_3(n)+1) = T(0) + sum_k=0^floor(log_3(n)(3n-5)/4^(log_3(n)
> - k) etc.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
