0
$\begingroup$

enter image description here

Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due tolog(n!) = Θ(nlogn). Any help is much appreciated.

$\endgroup$
  • 1
    $\begingroup$ I don't get how you find the middle step from the left one. I mean it is true, but I don't get what calculation lead to having this exponent 5 inside the log. In any case $\log((n!)^5n^{10}) = 10\log(n) + 5\sum_{i=1}^n\log(i) = \Theta(n\log(n)) = \Omega(n) = \Omega(n^{2/3})$. (And as usual with these Landau notations, equality is not to be interpreted as a real equality, but more as membership/subset relationships) $\endgroup$ – Tassle Aug 29 at 21:20
  • $\begingroup$ @Tassle $\log((n!)^5n^{10})=5\log(n!)+10\log n=\Theta(n\log n + \log n) = \Theta(n\log n)=\Theta(25n\log n)=\Theta(5n\log n^5)$. Though I'm not sure why they didn't stop at $\Theta(n\log n)$. $\endgroup$ – David Richerby Aug 30 at 10:47
  • $\begingroup$ Oh yes I know how to establish these "equalities" of course (that's why I said "it is true"), but what I was wondering about is what would lead you to write this in the first place, what "natural" calcultion leads to this constant appearing (other than just arbitrarily multiplying by some constant). $\endgroup$ – Tassle Aug 30 at 12:14
2
$\begingroup$

Remember that $\Theta(5n \log n^5) = \Theta(n \log n)$, since constant factors don't matter.

Then $\Theta(n \log n) = \Omega(n \log n)$, by the definition of big theta.

$\Omega(n \log n) = \Omega(n)$, because log is monotonic increasing (so we can remove it and still have a valid lower bound).

Finally, $\Omega(n) = \Omega(n^{2/3})$, by the properties of power functions.

$\endgroup$
  • $\begingroup$ Thanks a lot for the explanation! $\endgroup$ – Νίκος Τιτομιχελάκης Aug 31 at 16:01
  • $\begingroup$ @ΝίκοςΤιτομιχελάκης If the answer worked for you, remember that you can "accept" it by clicking the green checkmark on the left! $\endgroup$ – Draconis Aug 31 at 16:07

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.