Algorithmic Complexity Fundamentals

Algorithm performance is measured by execution duration and memory consumption. Time complexity quantifies the growth rate of operations relative to input size, while space complexity tracks auxiliary storage requirements. Engineers frequently accept higher memory usage to achieve faster runtimes. As input size N grows, constant factors and lower-order terms become irrelevant, leaving the dominant term to define the Big-O classification. Common benchmarks include O(1) for direct access, O(log N) for divide-and-conquer searches, O(N) for single-pass iterations, and O(N²) for nested comparisons. Scalable systems prioritize O(N) or O(log N) bounds. Space complexity follows identical asymptotic rules.

Binary Search

This technique operates exclusively on sorted, indexable sequences. By continuously dividing the search range in half, the target is either identified or the range colapses.

#include <stdio.h>

int locate_element(const int *sequence, int size, int target) {
    int lower_bound = 0;
    int upper_bound = size - 1;
    while (lower_bound <= upper_bound) {
        int pivot = lower_bound + (upper_bound - lower_bound) / 2;
        if (sequence[pivot] == target) return pivot;
        else if (sequence[pivot] < target) lower_bound = pivot + 1;
        else upper_bound = pivot - 1;
    }
    return -1;
}

The halving mechanism guarantees that the search space reduces exponentially, resulting in a logarithmic time complexity of O(log N).

Bubble Sort

This method iterates through the collection, comparing adjacent pairs and swapping them when out of order. Each full traversal pushes the largest unsorted value to its correct terminal position.

#include <stdio.h>

static void exchange(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void arrange_ascending(int *buffer, int length) {
    int i, j;
    int sorted_flag = 1;
    for (i = 0; i < length - 1; i++) {
        sorted_flag = 1;
        for (j = 0; j < length - i - 1; j++) {
            if (buffer[j] > buffer[j + 1]) {
                exchange(&buffer[j], &buffer[j + 1]);
                sorted_flag = 0;
            }
        }
        if (sorted_flag) break;
    }
}

Without early termination, the algorithm performs roughly N(N-1)/2 comparisons, yielding O(N²) time complexity.

Quick Sort

Quick sort selects a reference element (pivot) and partitions the dataset into two subsets: elements smaller than the pivot and elements larger. The partition process repeats recursively.

#include <stdio.h>

static void swap_elements(int *array, int idx1, int idx2) {
    int temp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = temp;
}

static int divide_partition(int *array, int low, int high) {
    int pivot_value = array[high];
    int insert_pos = low;
    for (int cursor = low; cursor < high; cursor++) {
        if (array[cursor] <= pivot_value) {
            swap_elements(array, insert_pos, cursor);
            insert_pos++;
        }
    }
    swap_elements(array, insert_pos, high);
    return insert_pos;
}

void quick_recurse(int *array, int low, int high) {
    if (low < high) {
        int split_index = divide_partition(array, low, high);
        quick_recurse(array, low, split_index - 1);
        quick_recurse(array, split_index + 1, high);
    }
}

Balanced partitions yield O(N log N) performance. Consistently poor pivot selection can degenerate the process to O(N²).

Merge Sort

Merge sort recursively splits the array in to halves until each segmant contains a single element, then merges adjacent segments while maintaining order.

#include <stdio.h>
#include <stdlib.h>

static void merge_sections(int *src, int left, int mid, int right, int *aux) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (src[i] <= src[j]) aux[k++] = src[i++];
        else aux[k++] = src[j++];
    }
    while (i <= mid) aux[k++] = src[i++];
    while (j <= right) aux[k++] = src[j++];
    for (i = left; i <= right; i++) src[i] = aux[i];
}

void merge_split(int *src, int left, int right, int *aux) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    merge_split(src, left, mid, aux);
    merge_split(src, mid + 1, right, aux);
    merge_sections(src, left, mid, right, aux);
}

The recursive depth is log N, and each level processes N elements, guaranteeing O(N log N) time. It requires O(N) auxiliary memory for the temporary buffer.

Heap Sort

Heap sort maps a complete binary tree onto a linear array. For a node at index i, its children reside at 2i + 1 and 2i + 2, while its parent is at (i - 1) / 2. A max-heap enforces the rule that every parent node exceeds its children.

#include <stdio.h>

static void sift_down_heap(int *heap, int limit, int node) {
    int largest = node;
    int left_child = 2 * node + 1;
    int right_child = 2 * node + 2;
    if (left_child < limit && heap[left_child] > heap[largest]) largest = left_child;
    if (right_child < limit && heap[right_child] > heap[largest]) largest = right_child;
    if (largest != node) {
        int temp = heap[node];
        heap[node] = heap[largest];
        heap[largest] = temp;
        sift_down_heap(heap, limit, largest);
    }
}

void build_heap_sort(int *data, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) sift_down_heap(data, length, i);
    for (int i = length - 1; i > 0; i--) {
        int temp = data[0];
        data[0] = data[i];
        data[i] = temp;
        sift_down_heap(data, i, 0);
    }
}

Building the initial structure takes O(N) time, and extracting each maximum requires O(log N) work. Combined, the algorithm runs in O(N log N) time with O(1) extra space.