34.2 Math Problems Out of Nowhere

A Math Problem

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})$

Another Math Problem

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)$.

Last Math Problem

In the previous problem, we showed that $log(N!) \in \Omega(N * logN)$. Now show that $N*logN \in \Omega(log(N!))$.

Proof:

• $log(N!)=log(N)+log(N-1)+...+log(1)$

• $N*logN=log(N)+log(N)+...+log(N)$

• Therefore $N*logN \in \Omega(log(N!))$

Omega and Theta

Given $N*logN \in \Omega(log(N!))$ and $log(N!) \in \Omega(N * logN)$. Which of the following can we say? A. $N*logN \in \Theta(log(N!))$ B. $log(N!) \in \Theta(N * logN)$ C. Both A and B D. Neither

Answer: C. Both A and B

Summary

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...