Register

Cormen Edition 3 Exercise 3.2 Question 3 (Page No. 60)

370 views

2 Answers

0 votes
0 votes
n! = omega(2^n)

n! = n * (n-1) * (n-2) * .......2 * 1     >      2 * 2 * 2* 2*  ...... * 2 (n times)          ; n > 2, (n-1) > 2 , (n-3) >2

so, n! =  omega(2^n)

n! = n * (n-1) * (n-2) * .......2 * 1    <     n * n * n *n         *n   (n times)           ; n = n , n-1 <n ; n-2 <n ; n-3 < n

so , n! = big-O( n^n)
User Avatar
0 votes
0 votes

Attached Proofs for both the questions. Don’t get confused between big-oh and little-oh. Both are different notations.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
akash.dinkar12 asked Apr 4, 2019
183 views
Cormen Edition 3 Exercise 3.2 Question 8 (Page No. 60)
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$\Theta$($n$/$ln$ $n$)$.
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$$\Theta$$($$n$$/$$ln$ $n$$)$.
User Avatar
0 votes
0 votes
0 answers
2
akash.dinkar12 asked Apr 4, 2019
215 views
Cormen Edition 3 Exercise 3.2 Question 6 (Page No. 60)
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
User Avatar
0 votes
0 votes
1 answer
3
akash.dinkar12 asked Apr 4, 2019
309 views
Cormen Edition 3 Exercise 3.2 Question 5 (Page No. 60)
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
User Avatar
1 votes
1 votes
0 answers
4
akash.dinkar12 asked Apr 4, 2019
175 views
Cormen Edition 3 Exercise 3.2 Question 4 (Page No. 60)
Is the function $\lceil$ $lg$ $n$ $\rceil$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$!$ polynomially bounded ?
Is the function $\lceil$ $lg$ $n$ $\rceil$$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$$!$ polynomially bounded ?
User Avatar
Link Copied!