C
C
CS61B Textbook
Search
⌃K
Comment on page

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!)∈Ω(N∗logN)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!)>N2∗log((N2))log(N!)>\frac{N}{2}*log((\frac{N}{2}))
    .
  • Discarding the unnecessary constant, we have
    log(N!)>Ω(N∗log(N2))log(N!)>\Omega(N*log(\frac{N}{2}))
    .
  • From there, we have that
    log(N!)>Ω(N∗log(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
N∗log(N)N*log(N)
.

Last Math Problem

In the previous problem, we showed that
log(N!)∈Ω(N∗logN)log(N!) \in \Omega(N * logN)
. Now show that
N∗logN∈Ω(log(N!))N*logN \in \Omega(log(N!))
.
Proof:
  • ​
    log(N!)=log(N)+log(N−1)+...+log(1)log(N!)=log(N)+log(N-1)+...+log(1)
    ​
  • ​
    N∗logN=log(N)+log(N)+...+log(N)N*logN=log(N)+log(N)+...+log(N)
    ​
  • Therefore
    N∗logN∈Ω(log(N!))N*logN \in \Omega(log(N!))
    ​

Omega and Theta

Given
N∗logN∈Ω(log(N!))N*logN \in \Omega(log(N!))
 and
log(N!)∈Ω(N∗logN)log(N!) \in \Omega(N * logN)
. Which of the following can we say? A.
N∗logN∈Θ(log(N!))N*logN \in \Theta(log(N!))
 B.
log(N!)∈Θ(N∗logN)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∈Θ(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...
Previous
34.1 Sorting Summary
Next
34.3 Theoretical Bounds on Sorting
Last modified 7mo ago