Complexity

12.3. Complexity#

Complexity analysis estimates how runtime and memory grow as input size increases.

12.3.1. Why complexity matters#

Measured runtime depends on machine and environment. Complexity gives machine-independent growth behavior.

12.3.2. Big-O quick reference#

  • O(1): constant work

  • O(n): linear work

  • O(n log n): typical efficient sorting

  • O(n^2): nested loops over same data

12.3.3. Common patterns#

Single pass:

for (int i = 0; i < n; i++) { ... } // O(n)

Nested pass:

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) { ... } // O(n^2)

Halving loop:

while (n > 1) n /= 2; // O(log n)

12.3.4. Space complexity#

Track extra memory, not input storage:

  • fixed temporaries: O(1)

  • additional array of size n: O(n)

12.3.5. Practical use#

Use complexity to choose algorithms first, then benchmark with realistic data.

Footnotes