(Big O - Little o - Omega - Theta) Bounds Notation

𝑂 - Big O

𝑔(𝑛) is 𝑂(𝑓(𝑛))

• iff for some constants 𝑐 and 𝑛₀, 𝑔(𝑛) ≤ 𝑐·𝑓(𝑛) for all 𝑛 ≥ 𝑛₀
• 𝑓(𝑛) describes the UPPER bound for 𝑔(𝑛)
• growth rate of 𝑔(𝑛) ≤ growth rate of 𝑓(𝑛)

• 𝑔(𝑛) = 𝑛²
• 𝑔(𝑛) = 𝑛
• 𝑔(𝑛) = 1

𝛺 - Omega

𝑔(𝑛) is 𝛺(𝑓(𝑛))

• iff for some constants 𝑐 and 𝑛₀, 𝑔(𝑛) ≥ 𝑐·𝑓(𝑛) for all 𝑛 ≥ 𝑛₀
• 𝑓(𝑛) describes the LOWER bound for 𝑔(𝑛)
• growth rate of 𝑔(𝑛) ≥ growth rate of 𝑓(𝑛)

• 𝑔(𝑛) = 𝑛²
• 𝑔(𝑛) = 𝑛³
• 𝑔(𝑛) = 𝑛^𝑛

𝛩 - Theta

𝑔(𝑛) is 𝛩(𝑓(𝑛))

• iff 𝑔(𝑛) is 𝑂(𝑓(𝑛)) AND 𝑔(𝑛) is 𝛺(𝑓(𝑛))
• 𝑓(𝑛) describes the EXACT bound for 𝑔(𝑛)
• growth rate of 𝑔(𝑛) == growth rate of 𝑓(𝑛)

• 𝑔(𝑛) = 𝑛²
• 𝑔(𝑛) = 2𝑛²
• 𝑔(𝑛) = 10𝑛²

𝑜 - Little o

𝑔(𝑛) is 𝑜(𝑓(𝑛))

• iff 𝑔(𝑛) is 𝑂(𝑓(𝑛)) AND 𝑔(𝑛) is NOT 𝛩(𝑓(𝑛))
• 𝑓(𝑛) is the upper bound for 𝑔(𝑛) but that 𝑔(𝑛) can never be equal to 𝑓(𝑛)
• growth rate of 𝑔(𝑛) < growth rate of 𝑓(𝑛)

• 𝑔(𝑛) = 𝑛
• 𝑔(𝑛) = 𝑙𝑜𝑔(𝑛)
• 𝑔(𝑛) = 1