121 Week 15 - Big Ω and Θ Notations

Question 1

Formal definition of Big O

Answer 1

A function T(n) ∈ O( f(n) ) if there exists positive constants M and n0 such that for all n≥n0:
T(n) ≤ M * f(n)

Question 2

Meaning of Big O

Answer 2

The upper bound on growth rate of function - the worst case.

Question 3

Formal definition of Big Ω

Answer 3

A function T(n) ∈ Ω( f(n) ) if there exists positive constants M and n0 such that for all n≥n0:
T(n) ≥ M*f(n)

Question 4

Meaning of Big Ω

Answer 4

The lower bound on growth rate of function - the best case.

Question 5

Formal definition of Big Θ

Answer 5

A function T(n) ∈ Θ( f(n) ) if there exists positive constants M1, M2 and n0 such that for all n≥n0:
M1f(n) ≤ T(n) ≤ M2f(n)

Question 6

Meaning of Big Θ

Answer 6

The tight bound on growth rate of a function - it is the best case out of all the worst cases.
f(n) can be both an upper and lower bound for T(n) depending on the value of M it is multiplied by. M1f(n) is the lower bound, M2f(n) is the upper bound.

Question 7

What are Big O, Big Ω and Big Θ for a best case input for linear search

Answer 7

O(1) - At most, it takes constant time.
Ω(1) - It will always take at least 1 comparison.
Θ(1) - Since best case performance is exactly constant, we have a tight bound.

Question 8

What are Big O, Big Ω and Big Θ for a worst case input for linear search

Answer 8

O(N) - At most, it takes n comparisons in the worst case.
Ω(N) - It takes at least n comparisons.
Θ(N) - Since worst-case performance is exactly linear, we have a tight bound.

Question 9

What are Big O, Big Ω and Big Θ for an average case input for linear search

Answer 9

O(N) - The average case will never exceed linear time.
Ω(N) - It takes at least n/2 comparisons on average, which is still linear.
Θ(N) - The function grows linearly in expectation, so we have a tight bound.