Difficulty: Intermediate | Prerequisites: Sorting algorithms overview, basic C programming (arrays, functions, loops)
Theoretical time complexity (Big-O) tells you how an algorithm scales in principle, but it hides constant factors, cache effects, and hardware differences. Empirical runtime analysis fills that gap: you run the algorithms on real data, measure wall-clock time, and see how the numbers actually behave as input grows. This topic ties together your knowledge of sorting algorithms with practical measurement techniques in C, and it is the kind of experiment that builds intuition no textbook formula can replace.
You generate arrays of increasing size, sort copies of each array with every algorithm, and time each run using C's clock() function. Plotting the results reveals the practical difference between O(n²) and O(n log n) growth, which becomes dramatic as input size increases.
Empirical analysis
Measuring an algorithm's actual running time on real inputs, as opposed to theoretical analysis (Big-O), which describes growth rate abstractly. Think of it as: theory says "this should be fast," empirical analysis says "here is exactly how fast it was."
clock_t
A type defined in that stores processor time. The value returned by clock() represents the number of clock ticks the program has consumed.
CLOCKS_PER_SEC
A constant from that tells you how many clock ticks fit into one second on your system. You divide a tick count by this value to convert to seconds.
Controlled experiment
Running each algorithm on the same input data so that differences in timing reflect only the algorithm, not the data. In this context, it means copying the original random array before passing it to each sort.
Big-O tells you the growth rate but not the actual speed. Two O(n²) algorithms can differ by a large constant factor.
Hardware, compiler optimisation, and memory access patterns all affect real performance. Empirical results capture these effects.
Plotting runtime against input size makes the difference between O(n²) and O(n log n) visible: the quadratic algorithms curve upward steeply, while merge sort and quick sort stay comparatively flat.
Create arrays at several sizes with a fixed step between them. A typical set: 10,000, 20,000, 30,000, 40,000, 50,000, 100,000.
Fill each array with random integers using rand() from . The formula rand() % maxVal + 1 produces values in the range [1, maxVal].
Before passing the array to each sorting algorithm, copy it so every algorithm receives the same unsorted input. Sorting modifies the array in place, so without copying you would be timing sorts on already-sorted data after the first run.
The standard approach uses clock() from :
#include Usage pattern:
clock_t start, end;
start = clock();
bubbleSort(arrayCopy, n);
end = clock();
long ms = timediff(start, end);
printf("Sorting %d values took %ld ms for Bubble Sort\n", n, ms);
Key points about timediff:
It is not a library function. You define it yourself.
The cast to double before dividing avoids integer truncation.
Multiplying by 1000 converts seconds to milliseconds, which is necessary because fast algorithms on small arrays can finish in under a millisecond and would otherwise report 0.
O(n²) algorithms (bubble, selection, insertion) show runtime roughly quadrupling when input size doubles. For example, if 10,000 elements take 100 ms, 20,000 elements take roughly 400 ms.
O(n log n) algorithms (merge sort, quick sort) show runtime roughly doubling (plus a small logarithmic factor) when input size doubles.
At small sizes (e.g., 10,000), merge sort and quick sort may both report 0 ms because they finish too quickly for millisecond-resolution timing. This is expected, not a bug.
Insertion sort typically beats bubble sort and selection sort on the same data despite sharing the same O(n²) complexity, because it does fewer swaps on average.
Forgetting to copy the array before each sort, so later algorithms sort already-sorted data (making insertion sort appear artificially fast and potentially worsening quick sort)
Running other programs during timing, which introduces noise from CPU scheduling
Using too-small array sizes where all algorithms report 0 ms, making comparison impossible
Time conversion formula:
elapsed (ms) = ((end - start) / CLOCKS_PER_SEC) × 1000
Random number generation:
n = rand() % maxVal + 1 generates a value in [1, maxVal]
Expected growth pattern (doubling input):
Complexity | Expected time increase |
|---|---|
O(n²) | ~4× |
O(n log n) | ~2× (plus small log factor) |
This is how engineers benchmark sorting libraries before choosing one for production code. The same clock/measure/compare methodology applies to any algorithm comparison, not just sorting. Database query optimisers, for instance, use empirical profiling to choose between execution plans.
Students often think an algorithm that reports 0 ms is broken. It is not. It just finished faster than the timer's resolution. Use larger inputs or a higher-resolution timer.
Empirical results from one machine do not transfer directly to another. The relative ordering of algorithms usually holds, but absolute times will differ.
A single run is not conclusive. Random data can produce best-case or near-best-case input for some algorithms by chance. Running multiple trials and averaging is more reliable.
The timediff function in this lab is not part of the C standard library. Students sometimes search for it in documentation and get confused.
⚠️ Know the clock() / timediff pattern. You may be asked to write or complete timing code.
⚠️ Be able to predict the shape of the runtime plot: quadratic curve for O(n²) algorithms, near-linear for O(n log n).
⚠️ Understand why you must copy the array before each sort. This is a common conceptual question.
⚠️ If asked why merge sort and quick sort report 0 ms on small inputs, the answer is timer resolution, not algorithmic error.
True or False: timediff is a built-in C standard library function.
Fill in the blank: To convert clock ticks to milliseconds, divide by _______ and multiply by 1000.
True or False: If you sort the same array with bubble sort first and then pass it to quick sort without copying, quick sort's time is still valid.
Fill in the blank: When you double the input size for an O(n²) algorithm, the runtime roughly _______.
True or False: Empirical analysis can reveal constant-factor differences that Big-O notation hides.
Answers: 1. False (you define it yourself). 2. CLOCKS_PER_SEC. 3. False (quick sort would receive sorted data, distorting results). 4. Quadruples (4×). 5. True.
Q: Why do we measure time in milliseconds rather than seconds for this experiment?
A: Faster algorithms on smaller arrays finish in fractions of a second. Integer-second precision would report 0 for most runs, making comparison impossible. Milliseconds give enough resolution to see differences.
Q: What happens to your experimental results if you forget to copy the array before passing it to each sorting algorithm?
A: After the first sort, every subsequent algorithm receives already-sorted data. This makes insertion sort appear much faster than it would be on random data and can cause quick sort (with a first-element pivot) to hit its O(n²) worst case.
Q: Explain how you would generate a random integer between 1 and 500 in C.
A: Use n = rand() % 500 + 1; after including . The modulo produces a value in [0, 499], and adding 1 shifts the range to [1, 500].
Q: Why does the runtime plot for bubble sort curve upward much more steeply than the plot for merge sort?
A: Bubble sort is O(n²), so its runtime grows quadratically with input size. Merge sort is O(n log n), which grows much more slowly. The gap widens as n increases.
Q: What does CLOCKS_PER_SEC represent?
A: It is a constant defined in that gives the number of clock ticks per second on the current system. Dividing a tick difference by this value converts it to seconds.
This connects directly to algorithm analysis and Big-O notation: empirical measurement is the practical counterpart to theoretical complexity classes. It also reinforces the sorting algorithms unit by making their performance differences tangible. Later in the course, similar timing techniques apply when analysing search algorithms, graph traversals, and other data-structure operations.
empirical analysis, runtime experiment, clock_t, clock(), CLOCKS_PER_SEC, timediff, timing in C, algorithm benchmarking, sorting performance, O(n²) vs O(n log n), runtime plot, millisecond timing, rand(), random array generation, COP3502C, Computer Science I, UCF, experimental algorithm analysis