Big-O Notation

Definitions

1. A mathematical notation describing the upper bound of an algorithm's time or space complexity as input size grows. O(1) is constant, O(log n) is logarithmic, O(n) is linear, O(n log n) is linearithmic, O(n²) is quadratic, and O(2ⁿ) is exponential. Focuses on growth rate, not constant factors.

   In plain English: A way to describe how much slower an algorithm gets as you give it more data, ignoring the small details.

   Example: "The nested loop makes this O(n²) — with 100,000 items, that's 10 billion operations. We need an O(n log n) approach."

Related Terms

• Space Complexity
• Backtracking
• Big-O
• Binary Tree
• Graph
• Hash Table
• Shannon Entropy
• NP-Completeness
• Graph Theory