our main character: o, ω, O, Ω and Θ

DEFINITION

Asymptotic Notation
Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.

Why we use asymptotic notation instead of detailed run-time function?

  1. :fire: TRIGGER:
    • The function describe algorithm is too complicate to see how an algorithm performs.
    • We’re only interested in the broad headlines of how some function behaves。
  2. :star: MOTIVATION:
    • We find it is possible to classify these ‘complicate’ functions via ‘simple’ ones.
  3. :boom: ATTAMPTS:
    • Asymptotic Notation :heavy_check_mark:
  4. :sparkles: CONSEQUENCE:
    • Reduce clutter and simplify calculation.
    • Way of making precise, quantitative statements about efficiency properties of algorithms themselves.

How to use asymptotic notation?

There are 5 different asymptotic notation: o, ω, O, Ω and Θ. And they share some PROPERTIES.

  1. $x(g) = {f : N → R≥0 | {definition} {of} x}$ , where x is one of these five.
  2. So, f is x(g) technically means f ∈ x(g).

Then let’s see how to use each of them

  • Example case
    • f = o(g)
  • How to say
    • f is asymptotically smaller than / grows slower than g
    • In the limit, f is vanishingly small relative to g
  • Definition
    • ∀c > 0. ∃N. ∀n ≥ N. f (n) < cg(n)
  • Property
    • A robust statement about f and g. E.g. unaffected by scaling: f = o(g) ⇔ 3f = o(0.2g)
  • Memory tips
    • Little o
    • g 在增长级数上碾压 f
  • Example case
    • f = ω(g)
  • How to say
    • g is asymptotically larger than / grows faster than f
  • Definition
    • ∀C > 0. ∃N. ∀n ≥ N. f (n) > Cg(n)
  • Property
    • A robust statement about f , g. Same as Little o.
    • f = o(g) ⇔ g = ω(f )
  • Memory tips
    • Think ‘C = 1/c’
    • Compare: x < y if and only if y > x.
    • g 增长级数上永远小于 f
  • Example case
    • f = O(g)
  • How to say
    • f is O(g) ‘f grows no faster than g’
    • call g an asymptotic upper bound for f
  • Definition
  • ∃c > 0. ∃N. ∀n ≥ N. f (n) ≤ cg(n)
  • Property
  • f = o(g) implies f = O(g)
  • Notice
    • Different with Little o:
      • For o we require that any multiple of g eventually overtakes f .
      • For O it’s enough that some multiple of g does.
      • ∀c compare with ∃C
    • If f = O(n^2) is a tight upper bound, f = O(n^3) is true but not a - tight upper bound.
  • Memory tips
    • Big O
    • Loosely, can think of o as like <, O as like ≤.
    • g 在增长级数上和 f 类似，但会存在 g 的增长率大于 f 的情况
  • Example case
    • f = Ω(g)
  • How to say
    • f is Ω(g) ‘f grows no slower than g’
    • g is an asymptotic lower bound for f
  • Definition
    • ∃C > 0. ∃N. ∀n ≥ N. f (n) ≥ Cg(n)
  • Property
    • f = O(g) ⇔ g = Ω(f )
  • Memory tips
    • Ω(g) ≤ Θ(g) ≤ O(g)
    • g 在增长级数上和 f 类似，但会存在 g 的增长率小于 f 的情况
  • Example case
  • f = Θ(g)
  • How to say
    • f and g have ‘essentially the same growth rate’
    • g is an asymptotically tight bound for f
  • Definition
  • ∃c1, c2 > 0. ∃N. ∀n ≥ N. c1g(n) ≤ f (n) ≤ c2g(n)
  • Property
    • f = Θ(g) ⇔ g = Θ(f )
    • f is Θ(g) ⇔ f is O(g) and f is Ω(g)
  • Memory tips
    Memory tip

Other

  • for some runtime function T(n):
    • T(n) = O(g) says runtime is not essentially worse than g(n),
    • T(n) = Ω(g) says runtime is not essentially better than g(n).

If you have better memory tips, tell my in the comment. It will be great.