Big-Oh proof

  • #1
Moved from a non-homework section, so missing the template
To prove that n log n is big oh of log(n!), I did:
n log n <= C log(n!)
n log n/ log(n!) <= C

Let k = 1
n > k, so for n = 2
2 log 2 / log 2 <= C
2 <= C
C is an element of [2, infinity)
Taking C = 2 and k = 1
can we say, n log n <= 2 log(n!)
and hence n log n is big oh of log(n!) ?
 

Answers and Replies

  • #2
BvU
Science Advisor
Homework Helper
14,607
3,819
  • Like
Likes Pepper Mint
  • #3
Hi,
You can use Stirling's approximation as follows:
log(n)≅nlog(n)-n ∈O(nlog(n)) .
 

Related Threads on Big-Oh proof

  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
7
Views
790
  • Last Post
Replies
2
Views
1K
Replies
2
Views
1K
M
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
602
  • Last Post
Replies
0
Views
2K
Replies
2
Views
612
Top