Show Menu
Cheatography
  1. Home >
  2. Programming >

CPSC320 Cheat Sheet (DRAFT) by

Cheatsheet for CPSC320 midterm 1

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Gale-S­hapley:

Worst-­case: n2 iterations - when all employers have identical prefer­ences list
Best-case: n iterations - when all employers have distinct 1st place prefer­ences
 

Big-O, Ω, Θ

g(n) ∈ O (f(n)) if ⇒ g(n) ≤ c · f(n)
g(n) ∈ Ω (f(n)) if ⇒ g(n) ≥ d · f(n),
g(n) ∈ Θ (f(n)) if ⇒ d · f(n) ≤ g(n) ≤ c · f(n)

- g(n) ∈ Ω (f(n)) iff f(n) ∈ O (g(n))
- g(n) ∈ Θ (f(n)) iff g(n) ∈ O (f(n)) and g(n) ∈ Ω (f(n))
iff g(n) ∈ O (f(n)) and f(n) ∈ O (g(n))