Algorithm Analysis- Big O Notation and Performance

What Algorithm Analysis Actually Is

Every piece of software you've ever used runs on algorithms. Some are fast. Some are embarrassingly slow. The difference between a 2-second page load and a 20-minute wait often comes down to one thing: how the algorithm scales.

Algorithm analysis is the practice of measuring and predicting how code performs as input grows. It's not optional knowledge for developers who want to write software that doesn't embarrass them.

Big O Notation: The Language of Scale

Big O notation describes the worst-case growth rate of an algorithm. It tells you how many operations an algorithm needs relative to the input size n.

The "O" stands for "order of magnitude." That's it. Nothing fancy.

Why Worst-Case?

Because things go wrong. When you're analyzing performance, you plan for the worst. If your code handles 10 items fine but crashes at 10,000, that's a Big O problem.

The Complexity Hierarchy (Fast to Slow)

Here's what you're dealing with, from fastest to slowest:

• O(1) — Constant time. Input size doesn't matter.
• O(log n) — Logarithmic. Still fast. Binary search is the classic example.
• O(n) — Linear. Time grows directly with input.
• O(n log n) — Linearithmic. Most efficient sorting algorithms land here.
• O(n²) — Quadratic. Gets ugly fast with large inputs.
• O(2ⁿ) — Exponential. Completely unusable beyond tiny inputs.
• O(n!) — Factorial. The death sentence of algorithm performance.

Breaking Down Each Complexity

O(1) — Constant Time

Array access is O(1). Hash table lookup is O(1). These operations don't care how big your dataset is. The computer does the same work regardless of whether you have 10 items or 10 million.

This is what you want. But you can't always get it.

O(log n) — Logarithmic Time

Binary search cuts your problem in half with each step. Find a word in a sorted dictionary? Binary search. Search a sorted array of 1 million items? Takes at most 20 comparisons. That's O(log n).

O(n) — Linear Time

Simple loops. Finding the maximum in an unsorted array. Reading every item once. If you have 10 items, you do 10 operations. If you have 1 million, you do 1 million operations.

O(n log n) — Linearithmic

This is the best you can achieve for comparison-based sorting. Merge sort, quicksort, and heapsort all land here on average. Good enough for most real-world sorting tasks.

O(n²) — Quadratic Time

Nested loops doing O(n) work twice. Bubble sort. Comparing every item to every other item. With 1,000 items, that's 1 million operations. With 10,000 items, that's 100 million.

This is where things start falling apart.

O(2ⁿ) and O(n!) — The Unusable Zone

Fibonacci calculated recursively without memoization is O(2ⁿ). The traveling salesman problem solved brute-force is O(n!).

These algorithms are theoretical curiosities. In practice, you never run them on real data. You use approximations, heuristics, or completely different approaches.

Time Complexity vs. Space Complexity

Performance isn't just about speed. Memory usage matters too.

Time complexity measures how many operations. Space complexity measures how much memory you need. Sometimes you trade one for the other.

Quick sort is O(n log n) time but O(log n) space. Merge sort is O(n log n) time but O(n) space. You pick based on your constraints.

Comparing Complexities Side by Side

See that jump from O(n²) to O(2ⁿ)? That's the difference between "slow but usable" and "will never finish."

How to Analyze Any Algorithm

Here's the practical process:

1. Identify your input size — What is n? The number of items? The length of a string?
2. Count the operations — How many basic steps does the algorithm execute?
3. Drop the constants — O(2n) is O(n). O(n + 100) is O(n). Constants don't matter at scale.
4. Drop the lower-order terms — O(n² + n) is O(n²). The dominant term wins.
5. Focus on worst case — Unless stated otherwise, Big O assumes worst-case input.

Example: Finding Duplicates

You have an array and want to find if duplicates exist.

Approach 1: Nested loops. For each element, scan the rest of the array. That's O(n²).

Approach 2: Use a hash set. Insert each element, check if it exists first. That's O(n) time, O(n) space.

Same problem, completely different performance. The hash set solution scales. The nested loop doesn't.

Getting Started: What to Do Today

Stop writing code without thinking about scale. Here's your action plan:

• Read code with Big O glasses — Every loop you write, ask: how many times does this run? What happens if n is 1 million?
• Memorize the common complexities — O(1), O(log n), O(n), O(n log n), O(n²). Know them cold.
• Profile before optimizing — Use actual benchmarks. Your intuition about performance is often wrong.
• Learn the data structures — Arrays, hash tables, trees, graphs. Each has different performance characteristics.
• Practice on LeetCode or HackerRank — Work through easy problems until analyzing complexity becomes automatic.

What Most Developers Get Wrong

Assuming O(something) is the same as actual performance. O(n) can be slower than O(n²) for small inputs. Big O describes scaling behavior, not raw speed.

Ignoring constants. An O(n) algorithm that does 1 million operations per item is worse than an O(n²) algorithm that does 5 operations per item pair—until your input gets massive.

Forgetting about the dominant term. O(n³ + n²) is O(n³). The cubic term dominates. Cut it first.

The Bottom Line

Big O notation isn't academic nonsense. It's the vocabulary for discussing how code scales. When your application slows to a crawl with real users, understanding Big O is what helps you find the problem.

Learn to read complexity. Learn to spot O(n²) when you see nested loops. Learn when to use a hash table instead of an array. These skills separate code that works from code that scales.