CSCE 222 Lecture 2

From Notes
Jump to navigation Jump to search

« previous | Friday, January 21, 2011 | next »


Asymptotically Comparing Functions

Let f(n)=5n and g(n)=n2:

  • When n<5, f(n)>g(n)
  • Asymptotically, g "grows faster" than f, so g(n) ≥ f(n) when n>5
  • In general, we say f is asymptotically less than or equal to g if and only if there exists a natural number n0 such that f(n) ≥ g(n) for all n>n0 →
    f≼g ⇔ ∃ n0∈ℕ : f(n)≤g(n) ∀ n≥n0[1][2][3][4][5]
  • Therefore 5n≼n2

For more complex problems like 7n2+6n+2, take limit to infinity and put it in order notation: 7n2+6n+2 is order n2 (O(n2))


Big O

An upper bound on a function f:

f(n)=O(n)→f(n)≤Cn→f(n)≼n
Precise Definition: f(n) is big oh of (order) g(n) if and only if there exists a constant C and a natural number n0 such that |f(n)| ≤ C|g(n)| for all n>n0
f(n)=O(g(n))⇔∃ C;n0∈ℕ:|f(n)|≤C|g(n)| ∀ n≥n0
Precise definition

Big Ω

A lower bound on a function f [6]:

f(n)=Ω(n)→f(n)≥Cn→f(n)≽n
Precise Definition: f(n) is big omega of g(n) if and only if there exists a constant C and a natural number n0 such that |f(n)| ≥ C|g(n)| for all n>n0
f(n)=Ω(g(n))⇔∃ C;n0∈ℕ:|f(n)|≥C|g(n)| ∀ n≥n0
Note: f(n)=Ω(g(n))⇔g(n)=O(f(n))

Big Θ

Means that function has same asymptotic growth as another function up to multiplication by constants. Similar to squeeze theorem in Calculus for proof of convergence.

f(n)=Θ(g(n))⇒∃ L<∞:limn→∞|f(n)||g(n)|=L
f(n)=Θ(g(n))⇔∃ L,U;n0∈ℕ:L|g(n)|≤|f(n)|≤U|g(n)| ∀ n≥n0
Precise definition

Note

L|g(n)|≤|f(n)| ∀ n≥nLso f(n)=Ω(g(n))U|g(n)|≥|f(n)| ∀ n≥nUand f(n)=O(g(n))f(n)=Θ(g(n)) ∀ n≥max⁡(nL,nU)


Examples

Example 1

  • Claim 5n=O(n2)
  • Choose C=5 and n0=1
  • {5n<5n2|5n|≤5|n2|} true ∀ n≥1

Example 3

7n2+6n+2=O(n2)n3−3n+2=O(n3)(7n2+6n+2)(n3−3n+2)=O(n2⋅n3)=O(n5)

Example 4

(See Wikipedia:Binomial coefficient→)

(n2)=n(n−1)2=n22+n2=n22+O(n)=O(n2)

Order of dominance

  1. O(nn)
  2. O(n!)
  3. O(n2)
  4. O(nlog⁡n)
  5. O(n)
  6. O(n)
  7. O(log⁡n)
  8. O(1)

Comparing Functions

f(n)=g(n)+O(n)

This means that f(n)−g(n)≤n up to a constant factor


Footnotes

  1. ↑ ≼ (curved or soft version of ≤) means "is asymptotically less than or equal to"
  2. ↑ ⇔ means "if and only if" (iff)
  3. ↑ ∃ means "there exists"
  4. ↑ : means "such that"
  5. ↑ ∀ means "for all"
  6. ↑ comparison-based sorting algorithms need at least Ω(nlog⁡n) comparisons.