When Does n lg n Switch from Ω to O?

  • Thread starter Thread starter Ananthan9470
  • Start date Start date
  • Tags Tags
    Bound
AI Thread Summary
The discussion focuses on determining the values of 'a' for which n log n transitions from Ω to O in asymptotic notation. It is established that n log n satisfies O(n^1.261) and Ω(n^0.797). The conversation also highlights a useful logarithmic bound, ln x ≤ x^(1/e), which aids in understanding the relationship between logarithmic functions and polynomial bounds. Additionally, it notes that switching to a different logarithmic base, log_b n, can still be expressed in terms of the natural logarithm to find asymptotic bounds. Understanding these transitions is crucial for analyzing algorithmic complexity.
Ananthan9470
Messages
31
Reaction score
0
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!
 
Mathematics news on Phys.org
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
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top