Skip to content
Deadline to Die

Module 1: Big O Notation (The Speed Limit)

📚 Module 1: Big O Notation

Course ID: DSA-101
Subject: The Speed Limit

Imagine you have two friends who want to deliver a letter across the city.

  • Friend A: Walks to the destination.
  • Friend B: Drives a car.

If the distance is 10 miles, the car is faster. But what if the distance is 10,000 miles? Or what if there is a massive traffic jam? In programming, we need a way to talk about speed that doesn’t depend on how fast the “car” (The CPU) is. We use Big O.

🏗️ Step 1: The Three Most Common Limits

1. O(1) - Constant Time (The “Fastest”)

No matter how much data you have, the task takes the same amount of time.

  • Analogy: Looking at the first page of a book. It takes the same time if the book has 10 pages or 10,000 pages.

2. O(n) - Linear Time (The “Normal”)

As the data grows, the time grows at the exact same rate.

  • Analogy: Reading every page of a book. If you have twice as many pages, it takes twice as long.

3. O(n²) - Quadratic Time (The “Dangerous”)

If you double the data, the time increases by four times.

  • Analogy: Comparing every page of a book with every other page. If you have 10 pages, you make 100 comparisons. If you have 20 pages, you make 400!

🏗️ Step 2: The Ranking (Fast to Slow)

  1. O(1) - Constant (Instant)
  2. O(log n) - Logarithmic (Very Fast - Binary Search)
  3. O(n) - Linear (Fair)
  4. O(n log n) - Linearithmic (Good - Efficient Sorting)
  5. O(n²) - Quadratic (Slow - Nested Loops)
  6. O(2ⁿ) - Exponential (Terrible - Brute Force)

🏗️ Step 3: Why do we ignore constants?

In Big O, we only care about the Long Term Trend.

  • O(2n+5)O(2n + 5) becomes just O(n)O(n).
  • Because when nn is 1 billion, that ”+ 5” and that “2x” don’t really matter compared to the massive scale of nn.

🥅 Module 1 Review

  1. Big O: A mathematical way to describe how much slower an algorithm gets as the input grows.
  2. Growth Rate: We care about the “Shape” of the curve, not the exact seconds.
  3. Worst Case: We usually talk about the worst-case scenario so we are never surprised by bad performance.

:::tip Slow Learner Note If you see a single for loop, it’s usually O(n). If you see a for loop inside another for loop, it’s usually O(n²). Simple! :::