# 34.2 Math Problems Out of Nowhere

## A Math Problem

<details>

<summary>Is <span class="math">N!\in \Omega((\frac{N}{2})^\frac{N}{2})</span>Prove your answer. [Recall that ∈ Ω can be informally be interpreted to mean >=. In other words, does factorial grow at least as quickly as <span class="math">(\frac{N}{2})^\frac{N}{2}</span>?</summary>

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

</details>

## Another Math Problem

<details>

<summary>Given: <span class="math">N!>(\frac{N}{2})^\frac{N}{2}</span>, which we used to prove our answer to the previous problem. Show that <span class="math">log(N!) \in \Omega(N * logN)</span>. [Recall: log means an unspecified base]</summary>

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

</details>

## Last Math Problem

<details>

<summary>In the previous problem, we showed that <span class="math">log(N!) \in \Omega(N * logN)</span>. Now show that <span class="math">N*logN \in \Omega(log(N!))</span>.</summary>

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

</details>

## Omega and Theta

<details>

<summary>Given <span class="math">N*logN \in \Omega(log(N!))</span> and <span class="math">log(N!) \in \Omega(N * logN)</span>. Which of the following can we say?<br><br>A. <span class="math">N*logN \in \Theta(log(N!))</span><br>B. <span class="math">log(N!) \in \Theta(N * logN)</span><br>C. Both A and B<br>D. Neither</summary>

Answer: C. Both A and B

</details>

## Summary

We’ve shown that $$N\*logN \in \Theta(log(N!))$$.

* In other words, these two functions grow at the same rate asymptotically.&#x20;

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