34.2 Math Problems Out of Nowhere

A Math Problem

Is N!Ω((N2)N2)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 (N2)N2(\frac{N}{2})^\frac{N}{2}?

10!

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

55

  • 5 * 5 * 5 * 5 * 5

N!>(N2)N2N!>(\frac{N}{2})^\frac{N}{2} for large N, therefore N!Ω((N2)N2)N!\in \Omega((\frac{N}{2})^\frac{N}{2})

Another Math Problem

Given: N!>(N2)N2N!>(\frac{N}{2})^\frac{N}{2}, which we used to prove our answer to the previous problem. Show that log(N!)Ω(NlogN)log(N!) \in \Omega(N * logN). [Recall: log means an unspecified base]

We have that N!>(N2)N2N!>(\frac{N}{2})^\frac{N}{2}

  • Taking the log of both sides, we have that log(N!)>log((N2)N2)log(N!)>log((\frac{N}{2})^\frac{N}{2}).

  • Bringing down the exponent we have that log(N!)>N2log((N2))log(N!)>\frac{N}{2}*log((\frac{N}{2})).

  • Discarding the unnecessary constant, we have log(N!)>Ω(Nlog(N2))log(N!)>\Omega(N*log(\frac{N}{2})).

  • From there, we have that log(N!)>Ω(Nlog(N))log(N!)>\Omega(N*log(N)). [since log(N2)log(\frac{N}{2}) is the same thing asymptotically as log(N)log(N)]

In other words, log(N!)log(N!) grows at least as quickly as Nlog(N)N*log(N).

Last Math Problem

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

Proof:

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

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

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

Omega and Theta

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

Answer: C. Both A and B

Summary

We’ve shown that NlogNΘ(log(N!))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 updated