Remember
Register
Algorithms Q&A
Smart HCM Software
Get the course textbook
Questions
Unanswered
Ask a Question
Lecture Notes
Not Exponential, on Twitter
All categories
Asymptotic Analysis
(22)
Divide & Conquer
(9)
Greedy Algorithms
(2)
Dynamic Programming
(7)
Backtracking/DFS/BFS
(2)
Branch & Bound
(2)
Graph Theory
(15)
NPCompleteness
(4)
Most popular tags
timecomplexity
asymptoticnotation
recurrencerelations
loops
graph
asymptoticanalysis
dynamicprogramming
analysis
vertexcoloring
greedy
log
exponent
mvcs
npcompleteness
mastertheorem
smalloh
nestedloops
sortedlists
example
recursive
graphcoloring
randomgraphgeneration
proxy
network
substitutionmethod
branchandbound
d&c
degreeconstrained
spanningtree
vertexcover
reduction
dfs
subtree
primenumbers
sqrt
lecture1
math
tree
count
minimize
floors
array
median
knapsack
trichotomy
eggs
searching
function
relation
gcd
tetris
log(n!) = Theta(nlogn)
+3
votes
How to explain this equation? It seems to be clear that log(n!) = O(n log n), since log (1.2.3.4.5....n) <= log (n.n.n.n...n) (n times).
However, how do we prove that log (n!) = Omega (n log n)
asymptoticnotation
asked
May 9
in
Asymptotic Analysis
by
shakexin
(
180
points)
edited
Jun 3
by
Amrinder Arora
Please
log in
or
register
to answer this question.
1 Answer
+1
vote
Best answer
log(n!) = log(1) + log(2) + ... + log(n1) + log(n)
You can get the upper bound by
log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
= n*log(n)
And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:
log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)
>= log(n/2) + ... + log(n/2)
= n/2 * log(n/2)
answered
Jun 15
by
Chris
AlgoStar
(
408
points)
selected
Jul 18
by
Amrinder Arora
Please
log in
or
register
to add a comment.
Related questions
+1
vote
2
answers
Given f(n) = o(g(n)), show that it is not necessary that log (f(n)) = o(log (g(n)))
asked
Sep 12, 2016
in
Asymptotic Analysis
by
Amrinder Arora
(
206
points)
asymptoticnotation
smalloh
log
+1
vote
1
answer
Time Complexity Analysis  2 (2nd by log n)
asked
Jan 19, 2016
in
Asymptotic Analysis
by
Jiajun Wang
(
216
points)
analysis
loops
asymptoticnotation
0
votes
4
answers
Compare 2^n^2 and 10^n asymptotically
asked
Sep 10, 2016
in
Asymptotic Analysis
by
Amrinder Arora
(
206
points)
asymptoticnotation
exponent
+1
vote
4
answers
Given f(n) = o(g(n)), prove that 2^f(n) = o(2^g(n))
asked
Sep 12, 2016
in
Graph Theory
by
Amrinder Arora
(
206
points)
exponent
log
smalloh
asymptoticnotation
+1
vote
2
answers
Order these time complexities from best (lowest) to worst (highest)
asked
Aug 31, 2016
in
Asymptotic Analysis
by
Amrinder Arora
(
206
points)
asymptoticnotation
log
exponent
The Book: Analysis and Design of Algorithms

Presentations on Slideshare

Lecture Notes, etc
...