~/analysis/asymptotic-complexity

Asymptotic analysis, line by line.

Each class is annotated with the cost of every statement. Adding those costs gives T(n), and T(n) gives the asymptotic time complexity.

Writing & readingProcessingFour sorting algorithms
00 · Results

What the analysis found.

PartT(n)Complexity
Writing & reading (FileService)4n + 6cO(n)
Processing (Benchmarker)Array copies O(n) + each sortO(n) per copy
Selection Sort3n² + 3n + cO(n²)
Insertion SortNested while loop, O(n²)O(n²)
Merge Sortlog n levels × O(n) mergeO(n log n)
Quick SortO(n) partition, recursive halvesO(n log n)
01 · The writing and reading running time

FileService: O(n)

Reading delegates to the input validator, which is O(n). Writing loops over the array once, with a constant cost per record, so T(n) = 4n + 6c and the asymptotic time complexity is O(n).

Figure 1The writing and reading running timeClick to enlarge.
02 · The processing run time

Benchmarker: copy, time, sort.

Each fresh copy of the array costs O(n). Timer calls and print statements are O(1). The sort calls themselves are analysed below.

Figure 2The processing (demand score computation) run timeClick to enlarge.
03 · The sorting running time

Four algorithms, four derivations.

Selection Sort · O(n²)T(n) = 3n² + 3n + cThe nested loops each run up to n times, so the n² term dominates.
Insertion Sort · O(n²)Outer loop O(n), inner while O(n²)Shifting smaller elements right inside the outer loop gives O(n²).
Merge Sort · O(n log n)n per level × log n levelsHalving recursively gives log n levels, and merging at each level costs O(n).
Quick Sort · O(n log n)O(n) partition, recursive halvesEach partition is O(n), and the recursion over both halves gives O(n log n).
04 · Visualise it

How n, n log n and n² grow.

An interactive illustration of the three growth rates above. It plots basic operation counts, not milliseconds.

nn log₂ nn²
3,432
—more basic operations for n² than n log n when n = 3,432
n—
n log₂ n—
n²—