📏 Big-O Notation — "How Slow Does This Get?"

Before we meet any data structure, we need a way to talk about how a recipe behaves when the pile of toys gets huge. That's all Big-O is.

🧸 ELI5: Imagine you have 3 toys — checking every single one to find your favorite is quick, maybe 3 seconds. Now imagine you have 3 million toys. Big-O is just the answer to: "if I 1,000x the toys, does the search take 1,000x longer, the same time, or something in between?" It's not a stopwatch — it's a shape of growth. We use the letter n to mean "however many things you have."

🌍 Real life: Big-O is why a phone book with a million names is only slightly slower to search than one with a thousand names (binary search — O(log n)), but why checking every student against every other student in a class for "who has the same birthday" gets painful fast as the class grows (O(n²)).

Here's the full scale, from best to worst, each with something you already do in real life:

Why n matters at scale — say you have 1,000,000 items:

O(1)        ->  1 step            (instant, always)
O(log n)    ->  ~20 steps         (binary search on a million records)
O(n)        ->  1,000,000 steps   (scan everything once)
O(n log n)  ->  ~20,000,000 steps (a good sort)
O(n²)       ->  1,000,000,000,000 steps  (bubble sort on a million items — do NOT try this)

That jump from O(n log n) to O(n²) is the reason engineers care so much about picking the right data structure — it's the difference between a page loading instantly and a server timing out.

📝 Pseudocode (spotting Big-O by counting loops):

function example(list):        // n = length(list)
    for item in list:          // one loop over n items -> O(n)
        print(item)

function example2(list):
    for a in list:              // loop 1: n
        for b in list:          // loop 2 nested inside: n
            print(a, b)          // nested loops -> O(n * n) = O(n²)

🐹 Go (same shapes, real code):

package main

import "fmt"

// O(1) — constant time, no matter how big `nums` is
func firstItem(nums []int) int {
	return nums[0]
}

// O(n) — linear, one pass over every item
func sum(nums []int) int {
	total := 0
	for _, n := range nums {
		total += n
	}
	return total
}

// O(n²) — quadratic, a loop inside a loop
func hasDuplicatePair(nums []int) bool {
	for i := range nums {
		for j := range nums {
			if i != j && nums[i] == nums[j] {
				return true
			}
		}
	}
	return false
}

func main() {
	nums := []int{4, 8, 15, 16, 23, 42}
	fmt.Println(firstItem(nums))        // O(1)
	fmt.Println(sum(nums))              // O(n)
	fmt.Println(hasDuplicatePair(nums)) // O(n²)
}

⏱️ The rule of thumb: every topic below lists its own ⏱️ Complexity. When you're choosing a data structure or algorithm for a real project, ask "how big can n get?" — O(n²) is perfectly fine for 50 items and a real problem for 5,000,000.

🟢 BEGINNER

Big-O gave you the ruler for measuring "how slow does this get." This tier gives you the actual toy boxes — the containers and the two slowest ways to search and sort — that every fancier structure later in this guide is built on top of. None of these seven topics are hard; each one just solves exactly one "how do I organize/find/undo this" problem.

array = [10, 20, 30, 40]
read array[2]        // instantly returns 30

package main

import "fmt"

func main() {
	parkingSpots := [5]string{"Car", "", "Bike", "", "Truck"}
	fmt.Println(parkingSpots[2]) // "Bike" — instant lookup
}

#include <stdio.h>

int main(void) {
    const char *parkingSpots[5] = {"Car", "", "Bike", "", "Truck"};
    printf("%s\n", parkingSpots[2]); // "Bike" — instant lookup, same address-math trick
    return 0;
}