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₀ and c such that to the right of n₀, 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 such that 0 ≤  cg(n) ≤ f(n) for every n ≥ n₀ }.

As ? notation define lower bound, it is utilized to bind the best case running time of an algorithm.