Pattern #1

Time & Space Complexity

Understand how code behaves as data scales — Big-O notation, speed order, rules, and Go interview examples.

What is Complexity?

Complexity tells us: How code behaves when data becomes large.

Time → How much work?

Space → How much extra memory?

Time Complexity

“If users/data increase, how much more work does my code do?”

O(1) — Constant

Same amount of work every time.

x := arr[0]

👉 Direct access = O(1)

⚡ Production example: Getting a user from a map using their ID.

O(n) — Linear

Check every item once.

for _, v := range arr {
    fmt.Println(v)
}

👉 One full loop = usually O(n)

⚡ Production example: Searching 1 million users one by one means up to 1 million checks.

O(n²) — Quadratic

Loop inside another loop.

for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
    }
}

👉 Loop inside loop = usually O(n²)

Why bad? 1,000 items → 1,000 × 1,000 = 1,000,000 operations

⚡ Production example: Comparing every user with every other user becomes very slow as users grow.

O(log n) — Logarithmic

Reduce the problem by half each time (e.g. Binary Search).

1000 → 500 → 250 → 125 → ...

👉 Half every step = O(log n)

⚡ Production example: Finding one item in a sorted list without checking everything.

O(n log n)

Common with efficient sorting (Merge Sort, Quick Sort avg, Go sorting).

👉 Good sorting = usually O(n log n)

Easy Speed Order

Best → Worst:

O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2ⁿ)<O(n!)

💡 For interviews, remember mainly: O(1) < O(log n) < O(n) < O(n log n) < O(n²)

Small Rules

Rule 1: Ignore constants

O(2n) → O(n) | O(5n) → O(n)

Rule 2: Keep biggest term

O(n² + n + 10) → O(n²)

Rule 3: Loops one after another → Add

O(n) + O(n) = O(2n) → O(n)

Rule 4: Nested loops → Multiply

O(n) × O(n) = O(n²)

Rule 5: Halving → Log

n → n/2 → n/4 → n/8 → Usually O(log n)

Space Complexity

Extra memory used by the algorithm.

O(1) Space

Only a few variables.

sum := 0
max := 0

👉 Data grows, memory doesn't.

O(n) Space

Extra memory grows with input.

m := make(map[int]bool)

for _, v := range arr {
    m[v] = true
}

👉 Store n things = O(n) space

⚡ Production example: Keeping information for 1 million users in memory requires much more RAM than keeping a few variables.

Important Trade-Off

Sometimes we use more memory to make code faster.

Searching array: Loop → O(n) time

Using Hash Map: Lookup → O(1) avg time, Extra memory → O(n)

💡 More space can save time.

Interview Tips

  1. 1. Always say both: State both Time: O(n) and Space: O(1).
  2. 2. First identify loops: One loop = O(n), Nested loop = O(n²).
  3. 3. Look for halving: Binary search halving = O(log n).
  4. 4. Check extra data structures: Maps, Sets, or extra arrays add O(n) space.
  5. 5. Don't optimize blindly:Ask: “Can I reduce O(n²) to O(n)?” — very common interview goal.

Quick Interview Example

for i := 0; i < len(arr); i++ {
    for j := 0; j < len(arr); j++ {
        fmt.Println(arr[i], arr[j])
    }
}

Time: O(n²)

Space: O(1)

Why? Two nested loops → n × n. No extra growing memory → O(1).

Remember This

Direct access → O(1)

Half each time → O(log n)

One loop → O(n)

Good sorting → O(n log n)

Loop inside loop → O(n²)

Extra n items → O(n) space

🌟 Golden Rule: Think about what happens when n becomes very large.