The ?-Notation (Lower Bound)
This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n_{0} and c such that to the right of n_{0}, value of f(n) always lies on or above cg(n). Figure illustrates the plot of f(n) = ?(g(n)).
Figure: Plot of f(n) = ?(g(n))
Mathematically specking, for a given function g(n), we might define ?(g(n)) as the set of functions.
?(g(n)) = { f(n) : there presents constant c & n_{0} ≥ 0 such that 0 ≤ cg(n) ≤ f(n) for every n ≥ n_{0} }.
As ? notation define lower bound, it is utilized to bind the best case running time of an algorithm.