Algorithms & Complexity — C Programming Course

What you'll learn

Algorithms are procedures; complexity describes how their resource needs grow. Correctness comes first, then measurements and growth analysis guide improvements that matter.

By the end, you'll be able to:

Compare common time and space complexity classes
Implement overflow-safe binary search and insertion sort
Recognize divide-and-conquer and traversal patterns
Benchmark without mistaking one noisy timing for proof

Time & space complexity

Big O describes an upper growth trend as input size n becomes large. It omits constant factors and lower-order terms, so it complements—not replaces—measurement.

Approximate operation growth

n	log n	n	n log n	n²
10	≈ 4	10	≈ 33	100
1,000	≈ 10	1,000	≈ 10,000	1,000,000
1,000,000	≈ 20	1,000,000	≈ 20,000,000	10¹²

Class	Typical example
`O(1)`	Array indexing or stack push
`O(log n)`	Binary search in sorted data
`O(n)`	Linear scan or list traversal
`O(n log n)`	Efficient comparison sorting
`O(n²)`	All pairs or simple quadratic sorting

Searching

Linear search works on any sequence in O(n). Binary search repeatedly halves asorted search range, giving O(log n) comparisons.

binary_search.c

#include <stddef.h>
#include <stdio.h>

ptrdiff_t binary_search(const int values[], size_t count, int target) {
    size_t low = 0;
    size_t high = count; // half-open range [low, high)

    while (low < high) {
        size_t middle = low + (high - low) / 2;
        if (values[middle] == target) return (ptrdiff_t) middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle;
    }
    return -1;
}

int main(void) {
    int sorted[] = {3, 7, 12, 18, 25, 31, 44};
    printf("%td\n", binary_search(sorted, 7, 25));
    return 0;
}

Key idea

The half-open range [low, high) contains candidate indexes. Computinglow + (high - low) / 2 avoids the overflow risk of(low + high) / 2.

Watch out

Binary search is wrong on unsorted data, even if a few tests happen to pass. Preconditions are part of an algorithm's contract.

Sorting

Insertion sort grows a sorted prefix by moving one value into place. Its worst case is O(n²), but it is compact, stable, and effective for small or nearly sorted inputs.

insertion_sort.c

#include <stddef.h>
#include <stdio.h>

void insertion_sort(int values[], size_t count) {
    for (size_t i = 1; i < count; i++) {
        int current = values[i];
        size_t position = i;

        while (position > 0 && values[position - 1] > current) {
            values[position] = values[position - 1];
            position--;
        }
        values[position] = current;
    }
}

int main(void) {
    int values[] = {5, 2, 4, 6, 1, 3};
    insertion_sort(values, 6);
    for (size_t i = 0; i < 6; i++) printf("%d ", values[i]);
    putchar('\n');
    return 0;
}

Algorithm	Typical time	Extra space	Useful property
Insertion sort	O(n²)	O(1)	Simple; strong on small/nearly sorted data
Merge sort	O(n log n)	O(n)	Stable and predictable
Quicksort	O(n log n) average	O(log n) stack average	Fast practical partitioning
qsort	Implementation-defined algorithm	Implementation-defined	Standard generic interface

Divide & conquer

Divide-and-conquer algorithms split a problem, solve smaller parts, and combine results. Merge sort recursively sorts two halves then merges them in linear time.

merge_step.c

#include <stddef.h>

void merge(const int source[], int target[],
           size_t left, size_t middle, size_t right) {
    size_t i = left;
    size_t j = middle;
    size_t out = left;

    while (i < middle && j < right) {
        target[out++] = source[i] <= source[j] ? source[i++] : source[j++];
    }
    while (i < middle) target[out++] = source[i++];
    while (j < right) target[out++] = source[j++];
}

/* A full merge sort alternates source and target buffers while recursively
 * sorting [left, middle) and [middle, right), then merges those runs. */

Note

A correct merge maintains the invariant that the output prefix is sorted and contains exactly the consumed source elements.

Tree & graph traversal

Tree traversal differs by when the node is processed. For a binary search tree, inorder traversal visits keys in sorted order; preorder visits a parent before descendants.

tree_traversal.c

#include <stdio.h>

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

void inorder(const Node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->value);
    inorder(root->right);
}

void preorder(const Node *root) {
    if (root == NULL) return;
    printf("%d ", root->value);
    preorder(root->left);
    preorder(root->right);
}

Depth-first traversal uses recursion or an explicit stack
Breadth-first traversal uses a queue
General graphs need a visited set to avoid cycles
Traversal is O(V + E) with adjacency lists

Measure performance

Benchmark optimized builds, representative inputs, multiple repetitions, and the exact operation users care about. Prevent the optimizer from deleting the measured work.

timing.c

#include <stdio.h>
#include <time.h>

double elapsed_seconds(clock_t start, clock_t end) {
    return (double) (end - start) / CLOCKS_PER_SEC;
}

int main(void) {
    clock_t start = clock();

    volatile unsigned long long total = 0;
    for (unsigned long i = 0; i < 1000000UL; i++) total += i;

    clock_t end = clock();
    printf("total=%llu time=%.6f s\n", total, elapsed_seconds(start, end));
    return 0;
}

Timing varies by machine, compiler, optimization level, and system load.

Watch out

clock measures implementation-defined processor time granularity. Serious benchmarks may require a platform monotonic clock and a dedicated harness.

Choose by constraints

Start with required correctness and stable behavior
Estimate input sizes and operation frequency
Consider memory, allocation, cache locality, and implementation complexity
Profile the real workload to find the actual bottleneck
Keep the simpler algorithm when measured gains do not justify complexity

Tip

Better data organization often matters more than clever inner-loop code. Changing an O(n²) approach to O(n log n) usually beats micro-optimizing the quadratic version.

Recap & quick check

Key takeaways

Complexity describes growth; measurement reveals constants and real-system effects.
Binary search requires sorted data and shrinks a half-open candidate range.
Insertion sort is quadratic but useful for small or nearly sorted inputs.
Divide-and-conquer splits, solves, and combines smaller problems.
Choose algorithms from correctness, constraints, complexity, and measured workload.

Quick check

1. What prerequisite does binary search require?

2. What is insertion sort's worst-case time complexity?

3. Which structure supports breadth-first traversal?

4. Why benchmark multiple representative runs?

Phase 4 complete. Phase 5 begins with Module 18 — Debugging, Testing & Undefined Behavior, where correctness becomes a repeatable professional process.