The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Is the following statement valid? $$\log(n!) = \Theta(n \log n)$$
+3
votes
964
views
algorithms
timecomplexity
normal
asked
Aug 28, 2014
in
Algorithms
by
er_prashantshukla

964
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
2
Answers
+7
votes
Best answer
I think it is sterling's approximation
$$\ln N! = N \ln N  N + \ln \sqrt{2 \pi n} $$
answered
Sep 4, 2014
by
Arpit Dhuriya 1
selected
Oct 11, 2014
by
Arjun
comment
Please
log in
or
register
to add a comment.
+2
votes
n! corresponds to n*(n1)*(n2)*....*1 which is $\Theta (n^n)$. So by taking $\log$ to both terms, the answer comes out to be $\Theta(n \log n)$.
answered
Aug 28, 2014
by
vivek puri
comment
+2
It is true for big O. But for $\Theta$ notation can we say $n! = \Theta (n^n)$?
0
no such constant exists for n^n, whereas for the nlogn I think it is 1/2
Please
log in
or
register
to add a comment.
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
+1
vote
1
answer
1
How is the time Complexity of this problem O(n log log n)?
int A(int n){ for(i = 1; i < n; i++) for(j = 1; j < i; j *= 2) for(k = j; k >= 1; k /= 2) if(n = 0) return 1; else{ for(z = 0; z < n; z++){ // do something } } } How do find the complexity of this problem? The answer is supposed to be O(n log log n), but it maybe wrong.
asked
Nov 22, 2018
in
Algorithms
by
gmrishikumar

802
views
algorithms
timecomplexity
recurrence
programminginc
0
votes
1
answer
2
Solve the recurrence relation $B(n) = 3B(n/log_2(n))+\theta(n)$
What is the solution of following recurrence relation. $B(2) = 1$ $B(n) = 3B(n/\log_2(n))+\Theta(n)$​
asked
Mar 25, 2016
in
Algorithms
by
prateekdwv

211
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
3
Prove that for any constant c > 0, (log n)^c = o(n).
asked
Oct 4, 2018
in
Algorithms
by
Ojamajo Conan

74
views
algorithms
timecomplexity
0
votes
0
answers
4
How many levels are present for this algorithm assuming merge can be accomplished in O(n log(k)) time.
asked
Dec 28, 2016
in
Algorithms
by
Akriti sood

119
views
algorithms
timecomplexity
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
2k
Engineering Mathematics
8.2k
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.6k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.2k
Others
1.5k
Admissions
595
Exam Queries
562
Tier 1 Placement Questions
23
Job Queries
71
Projects
19
Unknown Category
1k
Recent Blog Comments
Can someone tell me how to check part B marks?...
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,497
answers
201,862
comments
95,319
users