Calculate big-$\Theta$ for $T(x) = \log(x2x!)$

Question

$T(x) = \log(x2x!)$

use the property of log, $\log(x2x!)$ is equivalent to $\log(2x) + \log(x!)$

My approach is to prove big-$O$ and big-$\Omega$ for $T(x)$,then big-$\Theta$ just follows.

If I want to calculate big-$O$ and big-$\Omega$ for $T(x)$, can I treat $\log(2x)$ as a constant and ignore it since it's growth rate is so slow compare to $\log(x!)$?

Note, your subject says "Big-$\Theta$", but $\Theta$ is not mentioned in the question. — Thomas Andrews, May 26 '13 at 18:28
no, it's $\log(x2x!)$, the factorial sign only refers to $x$ — user59036, May 26 '13 at 19:52

score 1 · Answer 1 · answered May 26 '13 at 20:00

1

You may simply write $$ \log(x!) = \log(x)+ \log(x-1)+ \cdots+ \log(1) < x\log(x). $$

Then, $$ \log(2x)+ \log(x!) < (x+2) \log(x), $$

which is $O(x \log(x))$ as $x \to \infty$.

answered May 26 '13 at 20:00

Berkheimer

2,086
17
31

score 0 · Answer 2 · answered May 26 '13 at 18:31

0

This is where Stirling's Approximation comes in handy. The result is that $$ \log(2x \cdot x!) = \Theta\left(x \log x + \log 2 + \log x\right) = \Theta\left(x \log x\right) $$

answered May 26 '13 at 18:31

Jon Claus

2,760

Calculate big-$\Theta$ for $T(x) = \log(x2x!)$

2 Answers2