Which notation gives an asymptotic lower bound on an algorithm’s running time?
Correct answer B. Big-Omega (Ω)
Explanation
Big-Omega says a function grows at least as fast as another, so it is a lower bound. Big-O is an upper bound, and Big-Theta is a tight bound that holds both above and below. Little-o is a strict upper bound. Any comparison-based sort, for instance, is Ω(n log n) in the worst case, which means no such sort can do better than that.
Answer checked How we write and check questions
Discussion