-2
$\begingroup$

i have a question - how i can prove that:

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

i try something like that:

$\log((n^2)!) = 2*(log(n)!)=\theta(2*(log(n)!)=\theta(n\ log(n)) $

$\ \theta(log(n!)^2)=\theta(log(n!)*log(n!)) = \theta(n\ log(n)) $

then we can see that is equal --> there are $\theta(n\ log(n))$

this is true?

$\endgroup$
  • $\begingroup$ log((𝑛2)!)=2∗(𝑙𝑜𝑔(𝑛)!) is wrong. $\endgroup$ – gnasher729 Jan 31 at 21:23
  • $\begingroup$ You can't do that, because $(n!)^2 < (n^2)!$ $\endgroup$ – HEKTO Jan 31 at 21:26
  • 2
    $\begingroup$ Not just <, but an awful lot less. $\endgroup$ – gnasher729 Jan 31 at 21:35
  • 2
    $\begingroup$ Welcome to StackOoverflow! This question has been downvoted due to poor formatting. It is not clear if you mean "big theta of" or "little o of" $\endgroup$ – Ṃųỻịgǻňạcểơửṩ Jan 31 at 21:42
1
$\begingroup$

$(n^2)!$ is the product of the numbers 1 to $n^2$.

$(n!)^2$ is the product of the numbers 1 to n, multiplied by the product of the numbers 1 to n again.

In the first product, we have $n^2 - n$ numbers ≥ n plus some others. In the second product we have 2n numbers ≤ n. So if we take the logarithm, the first is ≥ $(n^2 - n) log n$, the second is ≤ $2n log n$. So f(n) / g(n) ≥ (n-1)/2. Absolutely not Big-$\Theta$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Alternatively: $(n^2)!$ is the product of $n^2$ numbers. We can split the product into n groups 1 .. n, n+1 .. 2n, 2n+1 .. 3n, $n^2-n+1$ .. $n^2$. The product of the numbers in each group is ≥ n!, actually significantly greater than n! in some cases. So $(n^2)! ≥ (n!)^n$.

If we let f(n) = $log ((n^2)!)$ and g(n) = $log((n!)^2)$, then f(n) ≥ n log(n!), while g(n) = 2 log(n!), so f(n) / g(n) ≥ n/2. So f(n) is not o (g(n)), or $\Theta(g(n))$, but g(n) = o (f(n)).

| cite | improve this answer | |
$\endgroup$

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.