Asymptotic Analysis

“But if there’s something that frightens you, there are those that turn their eyes away and there are those who try to see through the fear and conquer it.”
— The Big O

Computer Science classes often study the performance of algorithms through the lens of Asymptotic Analysis. Many proofs in asymptotic analysis are sloppy; we take shortcuts, work with approximations, and almost never refer back to the official definitions. The only excuse is that, in practice, this still usually produces the right answer! In this section, we’ll be careful and precise about asymptotic analysis, which is great practice for writing proofs and working with quantifiers.

If ff and gg are functions from N\mathbb{N} to N\mathbb{N}, we say

f∈O(g)iff∃c>0  ∃m≥0  ∀i≥m  ( f(i)≤c⋅g(i) )f \in O(g) \quad\mathrm{iff}\quad \exists c{>}0\ \ \exists m{\geq 0}\ \ \forall i{\geq}m\ \ (\,f(i) \leq c\cdot g(i)\,)

(where cc is a real number, and mm and ii are natural numbers).

That is, f∈O(g)f\in O(g) is true iff ff stays below the scaled function c⋅gc\cdot g once we reach inputs larger than mm.

Intutively, f∈O(g)f\in O(g) means that ff grows no faster than [a constant multiple of] gg as the input value becomes arbitrarily large.

Example

Theorem: 2n+1∈O(n)2n+1 \in O(n).
That is to say, ( n↦2n+1 )∈O( n↦n )(\,n \mapsto 2n{+}1\,) \in O(\, n\mapsto n\,).

Proof (heavily annotated):

To show: ∃c>0  ∃m≥0  ∀i≥m  ( 2i+1≤c i )\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,2i{+}1 \leq c\,i\,).
Put c:=3c := 3 and m:=2m := 2.
To show: ∀i≥m   ( 2i+1≤c i )\forall i{\geq}m\ \ \ (\,2i{+}1 \leq c\,i\,).
Let i≥m=2i \geq m = 2 be given.
To show: 2i+1≤c i2i{+}1 \leq c\,i.
Then 2i+1≤2i+i=3i=c i2i+1 \leq 2i + i = 3i = c\,i.
Thus: ∀i≥m  ( 2i+1≤c i )\forall i{\geq}m\ \ (\,2i{+}1\leq c\,i\,).
So ∃c>0  ∃m≥0  ∀i≥m  ( 2i+1≤c i )\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,2i{+}1 \leq c\,i\,).
Therefore, 2n+1∈O(n)2n+1 \in O(n). QED

Proof (traditional compressed form): Put c:=3c := 3 and m:=2m := 2. Then for all i≥m=2i \geq m = 2, 2i+1≤2i+i=3i=c i2i+1 \leq 2i + i = 3i = c\,i as required. QED

There are three things to note about this example:

  1. The annotated proof is much more verbose then you would ever see in a real-life proof. But when first practicing these proofs, the annotations are extremely helpful to keep track of where we are in the proof, and where we should be going.
  2. One might wonder how we knew that cc should be 3 and mm should be 2. The answer is that the author of this proof didn’t know when the proof was first being constructed; it was only after playing around with the algebra that follows that it became clear that 3 and 2 would ensure that 2i+1≤c i2i+1 \leq c\,i for all i≥mi\geq m. The order that the proof is presented is often not the order in which the pieces were figured out!
  3. Infinitely many other choices of cc and mm would have worked as well (though not all of choices). However, since we are proving an existentially quantified formula, it suffices to find a single example that works.

Example

Theorem: 100n+1000∈O(n)100n+1000 \in O(n).
That is to say, ( n↦100n+1000 )∈O( n↦n )(\,n \mapsto 100n{+}1000\,) \in O(\, n\mapsto n\,).

Proof (heavily annotated):

To show: ∃c>0  ∃m≥0  ∀i≥m  ( 100i+1000≤c i )\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,100i{+}1000 \leq c\,i\,).
Put c:=200c := 200 and m:=10m := 10.
To show: ∀i≥m   ( 100i+1000≤c i )\forall i{\geq}m\ \ \ (\,100i{+}1000 \leq c\,i\,).
Let i≥m=10i \geq m = 10 be given.
To show: 100i+1000≤c i100i{+}1000 \leq c\,i.
Then 10≤i10 \leq i,
so 1000≤100i1000 \leq 100i,
and hence 100i+1000≤200i=ci100i + 1000 \leq 200 i = ci.
Thus: ∀i≥m   ( 100i+1000≤c i )\forall i{\geq}m\ \ \ (\,100i{+}1000 \leq c\,i\,).
So ∃c>0  ∃m≥0  ∀i≥m  ( 100i+1000≤c i )\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,100i{+}1000 \leq c\,i\,).
Therefore, 100n+1000∈O(n)100n+1000 \in O(n). QED

Definition

If ff and gg are functions from N\mathbb{N} to N\mathbb{N}, we define the function f+gf+g “pointwise.” That is, for every k∈Nk\in\mathbb{N} ,

(f+g)(k):=f(k)+g(k)(f+g)(k) := f(k) + g(k)

Example

Theorem: If f∈O(h)f\in O(h) and g∈O(h)g\in O(h) then f+g ∈ O(h)f+g \ \in \ O(h).

Proof (heavily annotated):

To show: ∀f,g:N→N   ( f∈O(h)∧g∈O(h) → f+g∈O(h) )\forall f,g:{\mathbb{N}{\to}\mathbb{N}}\ \ \ (\,f{\in}O(h)\land g{\in}O(h) \ \to \ f{+}g\in O(h)\,).
Let f∈O(h)f\in O(h) and g∈O(h)g\in O(h) be given.
That is, assume that ∃c>0  ∃m≥0  ∀i≥m  ( f(i)≤c h(i) )\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,f(i) \leq c\, h(i)\,)
and that ∃c>0  ∃m≥0  ∀i≥m  ( g(i)≤c h(i) )\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,g(i) \leq c\, h(i)\,) .
To show: f+g∈O(h)f{+}g\in O(h).
That is, to show: ∃c>0   ∃m≥0  ∀i≥m   ( f(i)+g(i)≤c h(i) )\exists c{>}0\ \ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ \ (\,f(i){+}g(i) \leq c\, h(i)\,) .
By assumption, there exist c1c_1 and m1m_1 such that ∀i≥m1  ( f(i)≤c1 h(i) )\forall i{\geq}m_1\ \ (\,f(i) \leq c_1\, h(i)\,)
and there exist c1c_1 and m1m_1 such that ∀i≥m2  ( g(i)≤c2 h(i) )\forall i{\geq}m_2\ \ (\,g(i) \leq c_2\, h(i)\,).
Put c:=c1+c2c := c_1 + c_2
and m:=max⁡{m1,m2}m := \max\{m_1, m_2\}.
To show: ∀i≥m   ( f(i)+g(i)≤c h(i) )\forall i{\geq}m\ \ \ (\,f(i){+}g(i) \leq c\, h(i)\,)
Let i≥mi \geq m be given.
To show: f(i)+g(i)≤c h(i)f(i){+}g(i) \leq c\, h(i)
Since i≥m≥m1i \geq m \geq m_1, f(i)≤c1 h(i)f(i) \leq c_1\, h(i).
Since i≥m≥m2i \geq m \geq m_2, g(i)≤c2 h(i)g(i) \leq c_2\, h(i).
So (f+g)(i)=f(i)+g(i)≤(c1+c2) h(i)=c h(i)(f+g)(i) = f(i)+g(i) \leq (c_1+c_2)\,h(i) = c\, h(i).
Thus ∀i≥m   ( f(i)+g(i)≤c h(i) )\forall i{\geq}m\ \ \ (\,f(i){+}g(i) \leq c\, h(i)\,)
Then ∃c>0  ∃m≥0  ∀i≥m  ( f(i)+g(i)≤c h(i) )\exists c{>}0\ \ \exists m{\geq}0\ \ \forall i{\geq}m\ \ (\,f(i){+}g(i) \leq c\, h(i)\,) .
So ∀f,g:N→N   ( f∈O(h)∧g∈O(h) → f+g∈O(h) )\forall f,g:{\mathbb{N}{\to}\mathbb{N}}\ \ \ (\,f{\in}O(h)\land g{\in}O(h) \ \to \ f{+}g\in O(h)\,) .
Therefore, f+g∈O(h)f+g \in O(h) for all ff and gg. QED.