Little-o Notation

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

f(n) = o(g(n)) means f(n) grows strictly slower than g(n).

◇Details / Theory

◇Strict Upper Bound.

f(n) = o(g(n)) means f(n) grows strictly slower than g(n). lim (n→∞) f(n)/g(n) = 0.
Example: n² = o(n³). n² is not o(n²).

◇Complexity

◇Common Pitfalls

Confusing little-o with Big-O — little-o is strictly less than, while Big-O allows equality. Forgetting that $f(n) = o(g(n))$ means $f(n)/g(n) \to 0$, not just $\leq$.

◇Summary

TL;DR — Little-o ($o$) gives a strict upper bound: $f(n) = o(g(n))$ means $f$ grows strictly slower than $g$. Unlike Big-O, equality of growth rates is excluded.

◇Links

Related: Source / Reference:

◇References & Navigation

• Previous Topic: ◇Lesson 1- Analysis of Algorithms
• Next Topic: ◇Little-omega Notation
• Related Notes: ◇Asymptotic Notation, ◇Big-O Notation