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.
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. 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).
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).
On Jul 21, 12:40 pm, Ashesh <ashesh.amba...@gmail.com> 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, 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.
> On Jul 21, 12:40 pm, Ashesh <ashesh.amba...@gmail.com> 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.
> On Jul 21, 8:38 pm, zpedja <zekal...@gmail.com> wrote:
> > 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)) ).
