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
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top