In Definition 5.1 we see what it means for a function to be an upper bound. An alternative definition provides a lower bound for a function: A function f(n) is Ω(g(n)) (read “big-omega of g” or “at...

In Definition 5.1 we see what it means for a function to be an upper bound. An alternative definition provides a lower bound for a function:

A function f(n) is Ω(g(n)) (read “big-omega of g” or “at least order g”), if and only if there exist two positive constants, c and n0, such that

f(n) ≥ c · g(n)

for all n ≥ n0.

What is a lower bound on the time it takes to remove a value from a Vector by index?