Defintions of Asymtotic notations

Introduction

This page is meant to serve as a reminder of the definitions of asymtotic notations.

• Θ - notation: Θ(g(n)) = {f(n) : there exists positive constants c₁, c₂ and n₀ such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ n₀}.
• O - notation: O(g(n)) = {f(n) : there exists positive constants c and n₀ such that 0 ≤ f(n) ≤ cg(n) for all n &ge n₀}
• Ω - notation: Ω(g(n)) = {f(n) : there exists positive constants c and n₀ such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n₀}
• o - notation: o(g(n)) = {f(n) : there exists positive constants c and n₀ such that 0 ≤ f(n) < cg(n) for all n &ge n₀}
• ω - notation: ω(g(n)) = {f(n) : there exists positive constants c and n₀ such that 0 ≤ cg(n) < f(n) for all n ≥ n₀}