Quick question about asymptotic growth

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Growth
Click For Summary
SUMMARY

The discussion confirms that (\lg n)! is in \mathcal{O}((\lg n)^{\lg n}) based on Stirling's formula. This conclusion holds true under the assumption that n is either a power of 2 or that the gamma function is applied to lg(n) + 1. The participants agree on the validity of this mathematical relationship, emphasizing the importance of Stirling's approximation in analyzing asymptotic growth.

PREREQUISITES
  • Understanding of asymptotic notation, specifically Big O notation.
  • Familiarity with Stirling's formula for approximating factorials.
  • Knowledge of logarithmic functions and their properties.
  • Basic concepts of the gamma function and its relation to factorials.
NEXT STEPS
  • Study Stirling's approximation in detail to understand its applications in asymptotic analysis.
  • Learn about the properties of logarithmic functions and their significance in algorithm analysis.
  • Explore the gamma function and its relationship to factorial growth.
  • Investigate other asymptotic notations such as \Theta and \Omega for a comprehensive understanding.
USEFUL FOR

Mathematicians, computer scientists, and students studying algorithm analysis or computational complexity who seek to deepen their understanding of asymptotic growth and related mathematical concepts.

Dragonfall
Messages
1,023
Reaction score
5
[tex](\lg n)!\in\mathcal{O}((\lg n)^{\lg n})[/tex] right?
 
Mathematics news on Phys.org
Right, you can get that from Stirling's formula. (Assuming that either n is a power of 2 or you use gamma(lg(n) + 1), of course.)
 
Excellent, thanks.
 

Similar threads

MHB Yes, $2^{2^{2^n}}$ is a good example for $p(n)$ and $q(n)$ could be $n!$.
  • · Replies 13 ·
Replies
13
Views
3K
Complexity of this heap algorithm
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Question about intersection of coordinate rings
  • · Replies 1 ·
Replies
1
Views
2K
MHB Proving $T(n)=O(n^2 \lg^2 n)$ Using Recurrence Relation
  • · Replies 2 ·
Replies
2
Views
2K
MHB Upper and Lower bound of the recursive relation
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Mathematical Connection between Cosmic Expansion and Exponential Growth
  • · Replies 24 ·
Replies
24
Views
3K
Undergrad How Large Can N Be for F(n) = Log N to Run in 1 Second?
  • · Replies 11 ·
Replies
11
Views
4K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
Graduate What type of function satisfy a type of growth condition?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate When Does n lg n Switch from Ω to O?
  • · Replies 1 ·
Replies
1
Views
2K