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).
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)) )
> 2) I need *the exact* (closed form) solution for this one:
>
> T(1)=2 (T(0)=1)
> T(n)=4T(floor(n/3)) + 3n - 5
>
> I have found a solution for the case when n is a power of 3, but it
> obviously doesn't work for the general case.
For the general case, all you need to do is take n=3^α + β for some
integer 0<=β<3 and some integral α. Then push this term under floor
and it will all fall into place beautifully (in this case, floor(n/3)
= floor( (3^α + β)/3 ) = floor( 3^(α-1) + β/3 ) = 3^(α-1) (think!!).
You must also keep in mind that α=floor(logbase3(n)).
The recurrence part looks pretty simple and I think you'll be able to
solve it on your own.
> I just don't know what to
> do with this floor function.The solution, I think, should be
> asymptoticaly equal to theta( n^(log3(4) ), since it is so for the
> case of n=3^k (k-natural number).
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
