Comment on page

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