Asymptotic Analysis

Saying an algorithm is “O(n)” is only part of the story. Does it always take linear time? What if the input is already sorted?

Asymptotic Analysis gives us a formal way to describe the bounds of an algorithm’s performance. It helps us answer: “What’s the best that can happen? What’s the worst? And what happens on average?”

1. The Three Cases

Let’s take Linear Search (finding a number in a list) as an example.

1. Best Case (Ω - Omega)

The item we are looking for is the first element in the list.

  • Time: 1 comparison.
  • Notation: Ω(1)

2. Worst Case (O - Big O)

The item is the last element, or not in the list at all. We have to check everything.

  • Time: n comparisons.
  • Notation: O(n)

3. Average Case (Θ - Theta)

The item is somewhere in the middle. On average, we might check n/2 items.

  • Time: n/2 comparisons. Since we drop constants, it’s still linear.
  • Notation: Θ(n)

[!IMPORTANT] In interviews and general discussions, when we ask for “Time Complexity”, we usually mean the Worst Case (Big O), because we want to know the performance guarantee.

2. Formal Notations

Big O (O) - Upper Bound

f(n) is O(g(n)) if, for large enough n, f(n) is always less than or equal to c × g(n).

  • Think: “Less than or equal to” (≤)
  • Used for: Worst-case analysis.

Big Omega (Ω) - Lower Bound

f(n) is Ω(g(n)) if, for large enough n, f(n) is always greater than or equal to c × g(n).

  • Think: “Greater than or equal to” (≥)
  • Used for: Best-case analysis.

Big Theta (Θ) - Tight Bound

f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)). The function grows at exactly the same rate.

  • Think: “Equal to” (=)
  • Used for: Exact growth rate (Average case often falls here).

3. Visualizing Bounds

See how the actual runtime f(n) is sandwiched between the Upper and Lower bounds.

Upper Bound O(g(n))
Actual Runtime f(n)
Lower Bound Ω(g(n))

Adjust the "Tightness" of the bounds:

4. Why do we usually ignore Best Case?

Because Murphy’s Law applies to software engineering: “Anything that can go wrong will go wrong.” If we optimize for the best case (item is at index 0), our users will inevitably search for the item at index n-1.

Always design for the Worst Case (or Average Case) to ensure reliability.

Next Steps

One of the most powerful algorithm design techniques involves a function calling itself. Let’s explore Recursion.

5. Deep Dive Strategy Lab: Asymptotic Analysis

Intuition Through Analogy

Think of this chapter like debugging a production outage timeline. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?