Textbook
For sufficiently large natural $n$, the functions satisfy $f(n)\ge0$ and $g(n)>0$. Membership $f\in\Omega(g)$ means that constants $c>0$ and $n_0$ exist with $f(n)\ge c g(n)$ for all $n\ge n_0$.
This is an asymptotic lower bound. For $f(n)=3n+7$, suitable constants are $c=3$ and $n_0=1$ because $3n+7\ge3n$. The multiplier need not be optimal: a smaller positive $c$ may work too.
A lower bound need not give a tight order. For example, $n^2\in\Omega(n)$ even though $n^2/n$ is unbounded above. “At least a linear scale” does not mean exactly linear growth.
The symbol $\Omega$ does not mean an algorithm’s best case. A cost function, such as worst-case time $T_{\mathrm{worst}}(n)$, must be specified before its lower bound. A lower bound for one algorithm also does not prove that no other algorithm can solve the problem faster.
For $g(n)>0$, a lower bound requires the ratio $f(n)/g(n)$ to stay above some positive constant on a tail. Taking $c=0$ is forbidden: it would make the claim empty for every nonnegative function. For example, the constant function 7 is not in $\Omega(n)$, because any $c>0$ eventually gives $n>7/c$, violating $7\ge cn$. Positive values alone do not establish a growth lower bound.
Definitions and notation: Mathematics for Computer Science.
Related concepts: Big O: an upper growth bound, Big Theta: a tight growth order.
In plain language
A lower bound places a floor below which the function cannot fall beyond a chosen threshold. A constant multiplier may lower that floor, but it must then support every later input size. For a procedure required to read every array element, those reads already establish unavoidable work in the chosen model. One slow run supplies no such proof: an antivirus may have woken up alongside the program, and its mood establishes no lower bound.
Example
The constructed function $3n+7$ counts abstract operations. Each state highlights its guaranteed linear part $3n$.
Big Omega: a lower growth bound
Input 1
Of ten operations, three already establish the lower floor.
Step 1 of 4: Input 1
Read all steps
Input 1
Of ten operations, three already establish the lower floor.
- n; lower bound; cost
- 13current10included
Input 2
The linear part grows to 6 and total cost to 13.
- n; lower bound; cost
- 26current13included
Input 10
Cost 37 is still at least 30.
- n; lower bound; cost
- 1030current37included
Tail bound
The nonnegative extra 7 makes the inequality hold for every n ≥ 1.
- c; n₀
- 3included1included
Removing the positive extra 7 from this function leaves its linear part. The remaining $3n$ never exceeds the original value, so it supplies a valid floor. The values 3, 6, and 30 change with the input while the coefficient 3 stays fixed. Any positive coefficient working on the whole tail suffices. Merely listing three successful checks would not establish that eventual guarantee.
The lower bound applies to the declared function and model. It does not automatically apply to every algorithm for the task.