0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Sep 8 '10 at 0:57
  • 2
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Sep 8 '10 at 1:00
  • $\begingroup$ Thanks, I tried to make it look nicer with your suggestions...hope it helps the readability. $\endgroup$
    – Sev
    Sep 8 '10 at 1:04
1
$\begingroup$

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?

$\endgroup$
19
  • $\begingroup$ 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? $\endgroup$
    – Sev
    Sep 8 '10 at 2:46
  • $\begingroup$ @Sev: Why do you need to take log again? what is $\log (a^n)$? $\endgroup$
    – Aryabhata
    Sep 8 '10 at 2:50
  • $\begingroup$ 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? $\endgroup$
    – Sev
    Sep 8 '10 at 2:53
  • $\begingroup$ @Sev: If log (n!) ~ nlogn, what is nlog(n!)? What is the log of that? $\endgroup$
    – Aryabhata
    Sep 8 '10 at 2:55
  • $\begingroup$ @Moron: nlog(n!) must be n* nlogn which is n^2 log n? $\endgroup$
    – Sev
    Sep 8 '10 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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