Big-Oh significance and limitation

Big-Oh notation: f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. It is an asymptotic upper bound on the growth of f. Example: 4n² + 5n + 2 = O(n²).

Significance

• Gives a worst-case guarantee: the algorithm will never take more than c·g(n) for large n.
• Machine independent, so algorithms can be compared on paper.
• Ignores constants and lower-order terms, giving a simple classification (O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)).
• Helps to choose the better algorithm for large inputs.

Limitations

• It is only an upper bound; it may be loose (n = O(n²) is true but not useful).
• Hides constant factors: an O(n) algorithm with a huge constant may be slower than O(n²) for practical n.
• Describes behaviour only for large n; for small inputs a "slower" algorithm may win.
• Worst case may be rare, so it can be pessimistic about average behaviour.
• Ignores memory hierarchy, I/O and other real-machine effects.