Time and Space Complexity in Programming

What is Time Complexity?

Time complexity means how much time (number of steps or operations) an algorithm will take as the input size increases. We usually express it in Big O notation: O(1), O(n), O(log n), O(n²) etc.

Example:

• Searching an element in an array one by one → O(n)
• Searching in a sorted array using binary search → O(log n)

What is Space Complexity?

Space complexity means how much extra memory (RAM, stack, heap) is required by the algorithm apart from the input data.

Example:

• Iterative factorial uses only a few variables → O(1) space.
• Recursive factorial keeps function calls in stack → O(n) space.

Why It Matters in Embedded Systems

In normal PC programming, we mostly care about speed. But in embedded systems, we work with:

• Limited CPU speed
• Very small RAM (sometimes just a few KBs)
• Strict real-time deadlines

That’s why both time and space complexities directly affect performance, reliability, and even power consumption.

Examples in Embedded Context

1. Linear Search vs Binary Search

// Linear Search

for (i = 0; i < n; i++) {
    if (arr[i] == key) return i;
}

// Time: O(n)
// Space: O(1)

// Binary Search (Iterative)

while (low <= high) {
    mid = (low + high) / 2;
    if (arr[mid] == key) return mid;
    else if (arr[mid] < key) low = mid + 1;
    else high = mid - 1;
}

// Time: O(log n)
// Space: O(1)

Example: If you are storing sensor calibration data in flash, binary search is faster and saves power.

2. Recursion vs Iteration

// Recursive factorial

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

// Time: O(n)
// Space: O(n) (stack usage)

// Iterative factorial

int fact_iter(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++)
        result *= i;
    return result;
}

// Time: O(n)
// Space: O(1)

Example: On a microcontroller with 2KB RAM, recursion can overflow the stack. Iteration is safer.

3. Sorting Algorithms

// Bubble Sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Time: O(n^2)
// Space: O(1)

Bubble Sort: O(n²) time, O(1) space → slower but no extra memory.

// Merge Sort
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

// Time: O(n log n)
// Space: O(n)

Merge Sort: O(n log n) time, O(n) space → faster but needs memory buffer.

Example: If array size is small, bubble sort may be good enough. But for large data, merge sort or quick sort is better – only if memory allows.

Quick Notes

1. Time Complexity → Number of steps.
2. Space Complexity → Extra memory needed.
3. Linear Search → O(n) time, O(1) space.
4. Binary Search → O(log n) time, O(1) space.
5. Recursion → Same time, but higher space (stack).
6. Iteration → Same time, but less space.
7. Bubble Sort → O(n²) time, O(1) space.
8. Merge Sort → O(n log n) time, O(n) space.
9. Embedded Rule → Balance speed + memory + real-time constraints.