C Time Complexity

How it works

Big O describes how a resource requirement grows with input size, ignoring fixed factors under a stated model. A scan of n records is linear; visiting every ordered pair is quadratic. This does not say that every small linear program is faster than every quadratic one. Cache locality, allocations, data distribution and constant work per operation matter. First choose an appropriate representation, establish correctness and identify a measured bottleneck before adding complexity to save an unimportant instruction.

Run it locally

Use a hosted C17 compiler in a separate lab folder. The command assumes a driver named cc; substitute gcc, clang or zig cc as appropriate. C does not currently run in Bhylu’s browser playground. Apache, PHP and MySQL are not needed for these C programs.

cc -std=c17 -Wall -Wextra -Wpedantic -Werror complexity.c -o lesson

On Windows, use -o lesson.exe and run .\lesson.exe in PowerShell. On Unix-like systems run ./lesson. Math-library linking differs by toolchain; GCC on many Unix systems needs -lm after the source.

Download the complete C source. File-writing labs must run in an empty private directory, away from existing reports.

Example

#include <stdio.h>

int main(void) {
    size_t count = 5;
    size_t scan_steps = 0, pair_steps = 0;
    for (size_t i = 0; i < count; ++i) { ++scan_steps; }
    for (size_t i = 0; i < count; ++i) {
        for (size_t j = 0; j < count; ++j) { ++pair_steps; }
    }
    printf("Scan: %zu; ordered pairs: %zu\n", scan_steps, pair_steps);
    return 0;
}

Expected result

Scan: 5; ordered pairs: 25

The fixture counts conceptual body executions instead of timing an extremely short loop. Doubling count doubles the scan work and quadruples the pair work under this model. A benchmark should use representative data and avoid counting output time as algorithm time unless output is actually the operation being studied. Include memory use and worst-case behaviour in a design decision.