5 votes 5 votes Algorithms algorithms time-complexity normal + – er_prashantshukla asked Aug 28, 2014 er_prashantshukla 2.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 7 votes 7 votes I think it is sterling's approximation $$\ln N! = N \ln N - N + \ln \sqrt{2 \pi n} $$ Arpit Dhuriya 1 answered Sep 3, 2014 • selected Oct 11, 2014 by Arjun Arpit Dhuriya 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 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)$. vivek puri answered Aug 28, 2014 vivek puri comment Share Follow See all 2 Comments See all 2 2 Comments reply Arjun commented Aug 28, 2014 reply Follow Share It is true for big O. But for $\Theta$ notation can we say $n! = \Theta (n^n)$? 2 votes 2 votes Marv Patel commented Sep 1, 2014 reply Follow Share no such constant exists for n^n, whereas for the nlogn I think it is 1/2 0 votes 0 votes Please log in or register to add a comment.