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] inamecom
* to Hyde...                  * http://www.enst.fr/~jberger
*******************************

Post a reply to this message