Proving $n^{n/2} = \mathcal{O}(n!)$ Without Stirling's Approx

  • MHB
  • Thread starter alyafey22
  • Start date
In summary, the conversation discusses the attempt to prove that $n^{n/2} = \mathcal{O}(n!)$ using Stirling's approximation, but the speaker's teacher is not satisfied with this approach. They suggest using a more elementary approach, such as using lower and upper integrals for $\sum_{j=1}^n \ln j$. The goal is to prove the inequality $\frac{n^{n/2}}{n!}\le 1$ for $n/2>3$.
  • #1
alyafey22
Gold Member
MHB
1,561
1
I wanted to prove that

$$n^{n/2} = \mathcal{O}(n!)$$

I used the Striling approximation but I don't think my teacher will be happy to see that. Can you suggest another approach that is more elementary.
 
Technology news on Phys.org
  • #2
ZaidAlyafey said:
I wanted to prove that

$$n^{n/2} = \mathcal{O}(n!)$$

I used the Striling approximation but I don't think my teacher will be happy to see that. Can you suggest another approach that is more elementary.

Consider the derivation of Stirling's approximation.
It consists of first taking the logarithm, and then finding lower and upper integrals for $\sum_{j=1}^n \ln j$.
It is fairly straight forward and can be applied here as well.So what you want to prove is that there are some $C$ and $N$ such that for each $n>N$:
$$\frac n 2 \ln n \le \ln(C n!) = \ln C + \sum_{j=1}^n \ln j$$

This follows if we can prove that:
$$\frac n 2 \ln n \le \ln C + \int_1^n \ln x\,dx = \ln C + n\ln n - n + 1$$
 
  • #3
ZaidAlyafey said:
I wanted to prove that

$$n^{n/2} = \mathcal{O}(n!)$$
\[
\frac{n^{n/2}}{n!}\le\frac{2^{n/2}}{(n/2)!}\le 1\text { if }n/2>3.
\]
 

Related to Proving $n^{n/2} = \mathcal{O}(n!)$ Without Stirling's Approx

1. What does it mean for $n^{n/2} = \mathcal{O}(n!)$?

When we say that $n^{n/2} = \mathcal{O}(n!)$, it means that the function $n^{n/2}$ is bounded above by a constant multiple of $n!$ for large values of $n$. In other words, the growth rate of $n^{n/2}$ is no greater than the growth rate of $n!$, as $n$ approaches infinity.

2. Why is proving $n^{n/2} = \mathcal{O}(n!)$ important?

Proving $n^{n/2} = \mathcal{O}(n!)$ is important because it helps us understand the complexity of algorithms and functions. In computer science and mathematics, big O notation is used to describe the worst-case time complexity of an algorithm or the growth rate of a function. By proving that $n^{n/2}$ is bounded above by $n!$, we can infer that any algorithm or function with a time complexity of $n^{n/2}$ or less is also bounded by $n!$, which can help us analyze and compare different algorithms and functions.

3. Why can't we use Stirling's approximation to prove $n^{n/2} = \mathcal{O}(n!)$?

Stirling's approximation is a mathematical formula that approximates the factorial function. While it is a useful tool for estimating large factorials, it is not a rigorous proof and may not be accurate for smaller values of $n$. Therefore, in order to prove $n^{n/2} = \mathcal{O}(n!)$ without relying on Stirling's approximation, we must use other methods and techniques.

4. What techniques can be used to prove $n^{n/2} = \mathcal{O}(n!)$ without Stirling's approximation?

One approach to proving $n^{n/2} = \mathcal{O}(n!)$ is to use mathematical induction. We can also use properties of logarithms and the binomial theorem to simplify the expression $n^{n/2}$ and show that it is bounded above by a constant multiple of $n!$. Another method is to use the fact that $n!$ can be written as a product of factors, and then use the properties of exponents to show that $n^{n/2}$ is bounded above by this product.

5. Are there any other applications of proving $n^{n/2} = \mathcal{O}(n!)$ without Stirling's approximation?

Yes, there are several other applications of proving $n^{n/2} = \mathcal{O}(n!)$ without Stirling's approximation. For example, this result can be used to analyze the time complexity of algorithms in computer science and to understand the growth rate of certain mathematical functions. It can also be used to compare the efficiency of different algorithms or to prove other mathematical theorems.

Similar threads

C# Big O: find ##c## and ##n_0## if ##g(n)## is known
    • Programming and Computer Science
Replies
1
Views
1K
MHB How to Sort Elements of a Matrix in O(n) Time Complexity?
    • Programming and Computer Science
Replies
1
Views
1K
How Can We Efficiently Parallelize the N-Queens Problem?
    • Programming and Computer Science
Replies
11
Views
859
MHB Proving Asymptotic Bound: n*4^n=O(n!)
    • Programming and Computer Science
Replies
8
Views
2K
MHB Proving $\lg^2 n=o(2^{\sqrt{2 \lg n}})$ and $2^{2^{n+1}}=\omega(2^{2^n})$
    • Programming and Computer Science
2
Replies
59
Views
8K
What Is the Gaussian Distribution of an Ideal Gas?
    • Advanced Physics Homework Help
Replies
1
Views
922
I Runge-Kutta 4 w/ some sugar on the top: How to do error approximation?
    • Differential Equations
2
Replies
65
Views
3K
MHB Solving T(n) = O(n lg n) using substitution method?
    • Programming and Computer Science
Replies
2
Views
2K
Need help with N-body simulation
    • Programming and Computer Science
Replies
19
Views
3K
MHB Is $g(n)=O(g^5(n))$ true for all functions?
    • Programming and Computer Science
Replies
7
Views
2K

Hot Threads

Recent Insights

Back
Top