Time & Space Complexity

Complete Notes

Counting iterations → Big-O → TLE → a problem-solving checklist

How to read this

Every section builds on the one before it. Read top to bottom once and the whole chain — from “how long does my code take” to “which algorithm survives the time limit” — should click into place.

Contents

1. The Big Picture (why any of this matters)

2. Two Pieces of Basic Math You’ll Reuse Everywhere

3. The Worked Problem: Count the Factors of N

4. Turning Iterations Into Time

5. Iteration Counts for the Loops You’ll Keep Seeing

6. Big-O — the Clean Way to State Complexity

7. Space Complexity — Counting Extra Memory

8. TLE — Reading Constraints to Pick a Complexity

9. How to Approach a Problem (the whole loop in order)

10. One-Page Revision

1. The Big Picture (why any of this matters)

Before the math, hold this one idea in your head, because everything else hangs off it:

The two things we will measure for every algorithm:

• Time Complexity (TC) — how the number of iterations grows with N.
• Space Complexity (SC) — how much extra memory the algorithm uses as N grows.

Both are expressed with Big-O, which we build up to in section 5. We start with plain counting.

2. Two Pieces of Basic Math You'll Reuse Everywhere

2.1 Sum of the first N natural numbers

Quick check with N = 6: 1 + 2 + 3 + 4 + 5 + 6 = 21, and 6 × 7 ÷ 2 = 21. ✓

Where the formula comes from (Gauss's trick)

Write the sum forwards, then write it again backwards underneath, and add column by column:

Every column adds to (N + 1), and there are N columns. So:

Concretely, 1 + 2 + … + 100: the columns each make 101, there are 100 of them, so 2S = 101 × 100, giving S = 101 × 50 = 5050.

2.2 How many integers are in a range?

Count the integers in [3, 8] with both ends included: 3, 4, 5, 6, 7, 8 → that's 6 numbers. Notice 8 − 3 + 1 = 6.

The +1 is there because both endpoints are counted. Forgetting it is the classic off-by-one mistake.

3. The Worked Problem: Count the Factors of N

This single problem teaches the whole lesson: a slow way, a key observation, and a fast way. Keep it as your reference example.

What a factor is

A factor of N is a number that divides N with no remainder. A few examples to lock in the pattern:

In each case we are really asking: of the numbers 1 to N, which ones divide N? That immediately suggests a loop.

3.1 Approach 1 — check every number from 1 to N (brute force)

The loop body runs once per value of i, from 1 to N. So this does N iterations. Simple — but as we'll see, painfully slow for large N.

3.2 The key observation — factors come in pairs

Factors aren't scattered randomly. Whenever i divides N, the partner N / i is automatically a factor too, because:

Watch the pairs for N = 24. As i climbs, its partner N / i falls to meet it:

After i = 4 the pairs simply repeat in reverse (4×6 is the same pair as 6×4). Everything past that point is wasted work. The turning point is exactly where i meets N / i.

Same story for N = 100, but here the pair meets cleanly in the middle:

Adding those up: 2 + 2 + 2 + 2 + 1 = 9 factors of 100 (1, 2, 4, 5, 10, 20, 25, 50, 100). This exposes the one edge case:

3.3 Where exactly does the loop stop?

We stop the moment i reaches its own partner. That stopping line is:

So the loop only needs to run from 1 up to √N. For N = 24 that's i = 1 to 4; for N = 100 that's i = 1 to 10. We test i * i <= N in code so we never have to compute a square root.

3.4 Approach 2 — loop only up to √N (optimized)

Now the loop body runs only √N times instead of N. Same answer, far fewer iterations. Hold on to both iteration counts — N vs √N — because section 4 turns them into real seconds.

4. Turning Iterations Into Time

“√N is fewer than N” only matters if we can feel it in seconds. Use this rule of thumb as your clock:

Scaling the clock

Everything else is proportion. If 10⁸ iterations take 1 second, then 10⁹ (ten times more) take about 10 seconds:

Push it further. Suppose a brute-force method needed 10¹⁸ iterations:

Three hundred years for one answer is obviously useless. Now compare it with the √N approach from section 3 on the very same input:

Why 10⁸? (the hardware reason)

Clock speed sets the ceiling. 1 GHz = 10⁹ cycles per second, and a typical processor runs around 2.4 GHz. Each cycle does roughly one simple operation, so the hardware can theoretically push close to 10⁹ iterations a second. We deliberately plan against the safer, rounder 10⁸ so real-world overhead doesn't push us over the limit.

5. Iteration Counts for the Loops You'll Keep Seeing

Time complexity is just “how many times the inner work runs, written in terms of N.” Here are the three shapes that cover most code. Learn to read them on sight.

5.1 A loop that grows one step at a time → N

A plain for i = 1 to N runs its body exactly N times. That's the brute-force factor loop from section 3.1.

5.2 A loop that halves each time → log₂N

Trace the value of i: it goes N → N/2 → N/4 → … → 2 → 1, then stops. Line up which iteration produces which value:

The loop ends when the value reaches 1. Set the k-th value to 1 and solve for k:

Takeaway: anything that repeatedly halves the problem runs in log N steps — which is tiny. log₂(10⁹) is only about 30.

5.3 A loop inside a loop → N²

For each of the N values of i, the inner loop does a full N iterations. Stack them up:

Total = N added to itself N times = N × N = N² iterations. Each extra nested level multiplies by another N (giving N³, and so on).

6. Big-O — the Clean Way to State Complexity

Big-O cares about behavior for huge N, where the algorithm choice is what decides the running time. (Think of searching a pattern of length 5 inside a 300-page book: about 500 × 300 = 150000 = 1.5 × 10⁵ character comparisons — the size blows up fast, so the growth rate is all that matters.)

6.1 Three steps to get the Big-O

1. Count the number of iterations as a formula in N.
2. Drop the lower-order terms (they're dwarfed by the biggest term once N is large).
3. Drop the coefficient of the highest-order term (constants don't change the growth rate).

Example — say an algorithm runs f(N) = 3N³ + 4N² + 2 iterations:

Why ignore constants? Two algorithms doing 2N and N / 2 iterations are both O(N) — the multiplier (2 or ½) doesn't change how the cost grows as N rises. Big-O reports the shape of the growth, not the exact count.

6.2 The complexity hierarchy (slowest-growing to fastest)

Memorize this ordering. Lower order = better (fewer iterations for large N). It's the ruler you measure every algorithm against:

So our factor counter went from O(N) down to O(√N) — a real move left along this line.

7. Space Complexity — Counting Extra Memory

Same idea as time, but for memory: how much extra space does the algorithm allocate as N grows? “Extra” means beyond the input and the output. Compare two ways to count the integers in a range [a, b] (answer = b − a + 1).

Approach 1 — just compute it

Extra memory used: a single integer c. That's a fixed amount — it does not grow with N. A constant amount of extra space is order N⁰ = 1:

Approach 2 — build an array first

This allocates an array of N integers. At 4 bytes each that's 4 × N bytes of extra memory, which grows directly with N:

Both functions return the same number, but Approach 1 wastes no memory while Approach 2 scales its memory with N. Same hierarchy and same drop-the-constant rules from Big-O apply to space.

8. TLE — Reading Constraints to Pick a Complexity

In assignments and contests, code that's too slow is rejected with TLE (Time Limit Exceeded):

This is the 10⁸-per-second rule biting you. The constraints printed with a problem tell you the largest N, and from that you can work out which complexities will survive before writing a line of code.

Worked example

Constraints: 1 ≤ N ≤ 10⁵ and time limit = 1 second. Test each candidate complexity at the worst case N = 10⁵:

9. How to Approach a Problem (the whole loop in order)

Everything above slots into one repeatable procedure. Run it in this order, every time:

1. Read the question and the constraints carefully.
2. Formulate an idea / logic.
3. Verify the correctness of that logic.
4. Mentally sketch the pseudocode or a rough idea of the loops.
5. Determine the time complexity from that pseudocode.
6. Check feasibility against TLE — in the worst case you can afford only about 10⁷ to 10⁸ iterations.
7. Re-evaluate the idea if it won't fit the time limit; otherwise proceed.
8. Code the idea — only once it's been judged feasible.

10. One-Page Revision

The whole chain, compressed. If you remember this page, you can reconstruct the rest.

Formulas

• Sum of first N naturals: 1 + 2 + … + N = N × (N + 1) ÷ 2.
• Integers in a range [l, r]: r − l + 1 (both ends included).
• Factor pairing: i × j = N, so j = N ÷ i — factors come in pairs, so loop only to √N ( i × i ≤ N ).
• Factors of 24: 8 of them — 1, 2, 3, 4, 6, 8, 12, 24.

The time clock

• ≈ 10⁸ iterations per second. 10⁹ → 10 seconds; 10¹⁸ → ≈ 317 years.
• Worst case budget: about 10⁷–10⁸ iterations.

Standard loop → complexity

• step-by-step loop → O(N)
• halving loop → O(log N)
• loop to √N → O(√N)
• loop inside a loop → O(N²)

Big-O in 3 steps

• Count iterations → drop lower-order terms → drop the leading coefficient. e.g. 3N³ + 4N² + 2 → O(N³).

The hierarchy

Space

• O(1) = constant / no extra space (a few variables). O(N) = linear (an array of N items, e.g. 4N bytes).

The Big-O family

• Big-O splits into TC (time complexity) and SC (space complexity); failing the time check shows up as TLE.