Big-Omega Notation

Big-Omega notation provides a way to measure the ‘lower limit’ or the floor function for the running time (or storage taken) of an algorithm. Mathematically, it is similar to the asymptotic lower bound. %%🖋 Edit in Excalidraw, and the dark exported image%%

Formal Definition §

Big-Omega Notation

$$f(n)\in \Omega (g(n))⟺\exists n_0,c>0,\forall n>n_0,f(n)\ge cg(n)$$

Note

• $f(n),g(n)$ = Growth Function $f(n)$
• $n_0$ = Initial n value for which $f(n)$ starts to overtake $g(n)$ (the floor function).
• $c$ = Scaling constant for which $f(n)$ can overtake $g(n)$ If the equation holds, $f(n)$ is said to be $\Omega (g(n))$ (‘Omega of’)

Like with Big-O Notation, any valid $g(n)$ works, but the tighter the lower bound, the better.

Examples §