The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
513 views
asked in Algorithms by (41 points) | 513 views

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 by (227 points)
selected by
+2 votes
n! corresponds to n*(n-1)*(n-2)*....*1 which is $\Theta (n^n)$. So by taking $\log$ to both terms, the answer comes out to be $\Theta(n \log n)$.
answered by (31 points)
It is true for big O. But for $\Theta$ notation can we say $n! = \Theta (n^n)$?
no such constant exists for n^n, whereas for the nlogn I think it is 1/2


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

32,545 questions
39,231 answers
109,311 comments
36,613 users