|
![](/i/fill.gif) |
Thorsten Froehlich wrote:
>
> lim 2n lg n > lim 2n + n lg n
> n->oo n->oo
>
> =>
>
> lim n lg n > lim 2n
> n->oo n->oo
>
This doesn't make any mathematical sense since all four limits are
infinity and therefore can't be compared. What can be said is that for a
big enough n, you have:
2n lg(n) > 2n + n lg(n)
and
n lg(n) > 2n
Moreover your implication goes the wrong way (ie the second inequation
implies the first, not the other way round).
> In fact you are falling in the same trap I fell at first when replying to
> Ron: Trying to compare these two functions based on big-O notation! But
> you simply cannot compare two functions with the same big-O with each other
> using big-O. Other methods are needed, i.e. limits will solve the problem
> for the worst case very well.
>
Limits won't solve the problem at all since they can't be compared.
OTOH you can probably get away with saying "for a big enough n..."
I'm not trying to say that one is better than the other, I haven't
computed it and I don't intend to. I'm just pointing out that this
particular argument doesn't work (at least in the way it is presented).
--
* Doctor Jekyll had something * mailto:ber### [at] iname com
* to Hyde... * http://www.enst.fr/~jberger
*******************************
Post a reply to this message
|
![](/i/fill.gif) |