What is Big O Notation?

Big O notation describes how fast an algorithm is, or how much memory it uses, as the input size grows. It's like rating a car's fuel efficiency — it tells you how performance changes as you drive more miles.

Why It Matters:

Big O helps you understand if your algorithm will scale. An algorithm that's fast with 10 items might be unusable with 10 million items.

Common Complexities:

• O(1): Constant time — instant, regardless of input size
• O(log n): Logarithmic — very fast, like binary search
• O(n): Linear — grows proportionally with input
• O(n log n): Linearithmic — efficient sorting algorithms
• O(n²): Quadratic — nested loops, gets slow fast
• O(2ⁿ): Exponential — very slow, avoid if possible

Examples:

• Looking up in a hash table: O(1) — instant
• Searching an array: O(n) — might check every item
• Nested loops: O(n²) — for each item, check all items

What Big O Doesn't Tell You:

• Exact runtime (just growth rate)
• Best case performance (usually worst case)
• Constants (O(100n) is still O(n))

FAQ

Is O(n) always better than O(n²)?

Usually yes, but for small inputs, the difference might not matter. Big O describes behavior as input grows large.

What's the difference between time and space complexity?

Time complexity is how runtime grows. Space complexity is how memory usage grows. Both use Big O notation.

Do I need to know Big O?

Yes! It's essential for interviews and helps you write efficient code. Understanding it makes you a better programmer.