# Asymptotic bound of n lgn

## Main Question or Discussion Point

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!!!

## Answers and Replies

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.

Ananthan9470