Comment on page

# 34.2 Math Problems Out of Nowhere

Is

$N!\in \Omega((\frac{N}{2})^\frac{N}{2})$

Prove your answer. [Recall that ∈ Ω can be informally be interpreted to mean >=. In other words, does factorial grow at least as quickly as $(\frac{N}{2})^\frac{N}{2}$

?10!

- 10 * 9 * 8 * 7 * 6 * … * 1

55

- 5 * 5 * 5 * 5 * 5

$N!>(\frac{N}{2})^\frac{N}{2}$

for large N, therefore $N!\in \Omega((\frac{N}{2})^\frac{N}{2})$

Given:

$N!>(\frac{N}{2})^\frac{N}{2}$

, which we used to prove our answer to the previous problem. Show that $log(N!) \in \Omega(N * logN)$

. [Recall: log means an unspecified base]

We have that

$N!>(\frac{N}{2})^\frac{N}{2}$

- Taking the log of both sides, we have that$log(N!)>log((\frac{N}{2})^\frac{N}{2})$.
- Bringing down the exponent we have that$log(N!)>\frac{N}{2}*log((\frac{N}{2}))$.
- Discarding the unnecessary constant, we have$log(N!)>\Omega(N*log(\frac{N}{2}))$.
- From there, we have that$log(N!)>\Omega(N*log(N))$. [since$log(\frac{N}{2})$is the same thing asymptotically as$log(N)$]

In other words,

$log(N!)$

grows at least as quickly as $N*log(N)$

.We’ve shown that

$N*logN \in \Theta(log(N!))$

.- In other words, these two functions grow at the same rate asymptotically.

As for why we did this, we will see in a little while...

Last modified 7mo ago