Big Ω and Θ Notations

Big-O Notation

• The formal definition of Big O: 

  • T(n) ∊ O(f(n)) if there are positive constants M and n₀ such that 

    • T(n) ≤ M×f(n) for all n ≥ n₀

Big Ω Notation

• The formal definition of Big Ω: 

 

• Let T(n) and f(n) be two positive functions from the integers or the real numbers to the real numbers 

• T(n) is Ω(f(n)) if even as n becomes arbitrarily large, T(n)'s growth is bounded rom below by f(n), meaning it grows no slower than f(n) 

• T(n) ∊ Ω(f(n)) if there are positive constants M and n₀ such that 

  • T(n) ≥ M×f(n) for all n ≥ n₀

Big Θ Notation

• The formal definition of Big Θ: 

  • Let T(n) and f(n) be two positive functions from the integers or the real numbers to the real numbers 

  • T(n) is Θ(f(n)) if even as n becomes arbitrarily large, T(n)'s growth is bounded from above and below by f(n), meaning it grows no faster and no slower than f(n) 

  • T(n) ∊ Θ(f(n)) if there are positive constants M1, M2 and n₀ such that 

    • M1×f(n) ≤ T(n) ≤ M2 ×f(n) for all n ≥ n₀

  • It means T(n) ∊ Θ(f(n)) if T(n) ∊ O(f(n)) AND T(n) ∊ Ω(f(n))

Big O, Big Ω, Big Θ Graphs

In General

Linear Search

When No Case is Mentioned:

Which are TRUE? 

• Linear search is O(n) 

  • TRUE: There is no input of size n for which the runtime is not bounded from above by n 

  • Best case O(1), O(log n), O(n), …. 

  • Average case O(n), O(nlog n), O(n^2), ….. 

  • Worst case O(n), O(nlog n), O(n^2), …..

• Linear search is Ω(1) 

  • TRUE: There is no input of size n that takes less than a constant amount of time 

  • True for every algorithm 

  • Best case Ω(1) 

  • Average case Ω(n), Ω(log n), Ω(1) 

  • Worst case Ω(n), Ω(log n), Ω(1)

• Linear search is Θ(n)

  • FALSE: There is an input of size n, the best case, specifically, for which the runtime is Θ(1) 

  • Best case Θ(1) 

  • Average case Θ(n) 

  • Worst case Θ(n)

Summary