Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Note: logs below are base 2. (Not sure how to do subscripts here)

Wondering if the below equation is true when thinking asymptotically (Computer Science)

$log_2((n!)^n) = O(n \sin(n \frac{\pi}{2}) + \log_2{n})$

But I'm not sure how to compute this.

I'm guessing we need to take the log of both sides of the following equation:

$log_2((n!)^n) < n sin(n (pi/2)) + log_2(n)$

getting us:

$log_2(log_2((n!)^n)) < log_2 (n sin(n (pi/2)) + log_2(n) )$

Not sure where to go from there.

share|improve this question
1  
You should know that all log have the same big O limit, as they differ by a constant. Secondly, an underscore (within math mode, that is $ signs) will get you to subscript. –  Asaf Karagila Sep 8 '10 at 0:57
2  
Also, I'd try and use Stirling's approximation for $n!$ and the fact that $log(n!^n) = nlog(n!)$, and try to work it from there. Or something like that. –  Asaf Karagila Sep 8 '10 at 1:00
    
Thanks, I tried to make it look nicer with your suggestions...hope it helps the readability. –  Sev Sep 8 '10 at 1:04

1 Answer 1

up vote 1 down vote accepted

If you are interested in computer science, a very useful thing to remember is that

$$ \log n! = \theta(n \log n) $$

Now given this, can you tell what $f(n)$ is, if $ \log (n!^{n}) = \theta(f(n))$?

How would that compare to the right hand side?

share|improve this answer
    
Theta(n log(n!)) -- but in my equation we need to take the log of that again, which gives us log(n log(n!))...any tips on where to go from there? –  Sev Sep 8 '10 at 2:46
    
@Sev: Why do you need to take log again? what is $\log (a^n)$? –  Aryabhata Sep 8 '10 at 2:50
    
because originally it was log (log((n!)^n)) -- now i see that log(n!^n) is n log n! but what about the outer log? –  Sev Sep 8 '10 at 2:53
    
@Sev: If log (n!) ~ nlogn, what is nlog(n!)? What is the log of that? –  Aryabhata Sep 8 '10 at 2:55
    
@Moron: nlog(n!) must be n* nlogn which is n^2 log n? –  Sev Sep 8 '10 at 2:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.