# Asymptotic bound of n lgn

Tags:
1. Oct 12, 2015

### Ananthan9470

When considering the asymptotic bounds for n lgn, for what value of a in na does n lgn satisfy O(na) and for what value does it satisfy Ω(na)?

For example n lgn = O(n1.261) but n lgn = Ω(n0.797). Can someone please tell me where for what a does Ω change to O? Also how does the answer change when you consider general logb instead of lg. Thanks!!!

2. Oct 13, 2015

### VKnopp

A good bound that has been found for the logarithm (in a form that might be useful to you) is the following,

$\ln x \leq x^{\frac{1}{e}}$

That of course implies,

$|x \ln x| \leq |x^{\frac{e+1}{e}}|$

Now review the mathematical definition of $f(x)=O(g(x))$. You'll get the answer for your first question.

If you switch to $\log_{b} n$ you can still express it in terms of the natural logarithm and that will help you determine an asymptotic bound for logarithms with different bases.

Hope this helped.