Please help me prove nlogn -n belongs to Omega nlogn-CodePudding

I try to solve this problem many times but I still don't have a solution.
The question as follows:

Use the definition of Big Omega to prove that

nlogn - n belongs to Omega of nlogn.

Thank you

CodePudding user response：

As follows:

f(n) =  n log n - n
    >=  n log n - 0.5 n log n, for all n > 100 (assuming log10 base)
     =  0.5 * n log n,
     =    c * n log n,         for c = 0.5, n > n0 = 100

To summarize:

f(n) >= c * g(n),              for all n > n0 = 100, and
                               with c = 0.5, and
                               with g(n) = n log n.

CodePudding user response：

When logn > 2, then 1/2 nlogn - n > 0. Adding 1/2 nlogn to both sides gives nlogn - n > 1/2 nlogn.

This proves that nlogn - n is Omega(nlogn) (with the constant 1/2, and N the smallest integer such that logN>2).