The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes
asked in Algorithms by (43 points) | 680 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 (215 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

Related questions

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

44,462 questions
49,919 answers
65,898 users