Question

prove using limit lemma that n^2 > nlogn given some epsilon > 0

Answer 1

Question : To prove using limit lemma that n² > n logn

Solution : Consider f(n) = n² and g(n) = n logn

So f(n) > g(n) which is small omega notation.

According to little omega if    equals infinity ( ) then , f(n) is greater than g(n)

// Eliminating n from numerator and denominator.

The limit becomes :

  

On applying limit value it is of the form   which is a special case and needs to be corrected.

For this L'Hopital's rule need's to be applied.

L 'Hopital Rule : Take derivative of both numerator and denominator individually until there is no occurence of a special case limit.

Derivative of numerator = 1 // as derivative of n is 1

Derivative of denominator = 1/n // as derivative of logn is 1 / n

Now the limit becomes :

            // As 1/ (1/n) equals n . n goes to the numerator

Applying limit :

   ( infinity ) .

So as per the limit method , if    equals infinity then f(n) is greater than g(n) .

Hence Proved.