Asymptotic bound of n lgn

  • #1

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

  • #2
12
2
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.
 
  • Like
Likes Ananthan9470

Related Threads on Asymptotic bound of n lgn

  • Last Post
Replies
4
Views
17K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
1
Views
918
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
3
Views
5K
Top