DAA Module 1 01 / 04

Introduction — why performance matters

The same task can run fast for small input and become impossible for large input. DAA focuses on growth, not just code.

← Index Next →
Key idea

Performance is a boundary between feasible and infeasible. Exact runtime depends on machine/language, but growth trend is machine-independent.

Growth Scalability Intractable
Try this thought experiment: - You have an algorithm doing ~ n² operations. - If n becomes 10× bigger, work becomes 100× bigger. Now imagine an algorithm doing ~ 2ⁿ operations. - If n increases by 10, work multiplies by ~ 1024×.
Mini interactive: “work explosion”

Move n and compare growth. (This is a simple calculator — plots come on the next page.)

n
50
Operations (approx)
n50
n²2500
2ⁿ1.13e+15

Notice: for moderate n, 2ⁿ becomes enormous — this is why exponential-time brute force often becomes infeasible.

Where we go next

Next we define what “input size n” means for different problem types, then we use the Growth Visualizer to compare functions.

Go to 02 — What is n? Go to 03 — Growth Visualizer