[prev] 53 [next]

Relatives of Big-Oh (cont)

Examples:
  • ¼n2 ∈ Ω(n2)
    • need c > 0 and n0 ≥ 1 such that ¼n2 ≥ c·n2 for n≥n0
    • let c=¼ and n0=1
  • ¼n2 ∈ Ω(n)
    • need c > 0 and n0 ≥ 1 such that ¼n2 ≥ c·n for n≥n0
    • let c=1 and n0=4
  • ¼n2 ∈ Θ(n2)
    • since ¼n2 belongs to Ω(n2) and O(n2)
  • ¼n2 ∉ Θ(n)
    • since ¼n2 does not belong to O(n)