1. Introduction
Time complexity describes how the running time of an algorithm grows as the size of its input, usually denoted n, increases. Rather than measuring exact seconds (which depends on hardware, compiler, and system load), time complexity abstracts away those details and expresses growth using Big-O notation, which captures the upper bound of an algorithm's growth rate for large n. Understanding time complexity is essential for writing efficient C programs and is a core topic in technical interviews, since it lets you predict how an algorithm will scale before you even run it.
Cricket analogy: Time complexity is like judging a bowler's economy rate rather than the exact clock time of an over, since Big-O abstracts away pitch conditions and crowd noise to predict how performance scales as overs increase.
2. Syntax
Big-O notation is written as O(f(n)), where f(n) describes
how the number of operations grows relative to input size n.
Common complexity classes, from fastest to slowest growth:
O(1) - constant time
O(log n) - logarithmic time
O(n) - linear time
O(n log n) - linearithmic time
O(n^2) - quadratic time
O(2^n) - exponential time3. Explanation
Big-O notation focuses on the dominant term as n grows large and ignores constant factors and lower-order terms, since those matter less as n approaches infinity. For example, an algorithm that does 3n + 5 operations is still O(n), because the constant 3 and the additive 5 become insignificant compared to n for very large inputs. Below is a code example for each major complexity class, with a short explanation of why it falls into that class.
Cricket analogy: Big-O ignoring constants is like saying a batsman's strike rate matters more than a few extra dot balls at the start of an innings — 3n+5 balls faced is still 'O(n) balls' since the +5 warm-up barely matters over a long knock.
O(1) — Constant Time
An O(1) operation takes the same amount of time regardless of input size, such as accessing an array element by index.
Cricket analogy: O(1) is like a scorer instantly reading a specific over's total from a numbered scoreboard slot without scanning every over — accessing an array element by index is exactly this constant-time lookup.
int getFirstElement(int arr[], int n) {
return arr[0]; /* one operation, regardless of how large n is */
}O(log n) — Logarithmic Time
An O(log n) algorithm reduces the problem size by a constant factor (commonly half) at each step, such as binary search.
Cricket analogy: O(log n) is like a selector narrowing down a 128-player trial pool to the final squad by cutting it in half at each round of evaluation, just like binary search halving the search space every step.
int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1; /* search range halves each iteration -> O(log n) */
}O(n) — Linear Time
An O(n) algorithm visits every element of the input exactly once, such as finding the maximum value in an array.
Cricket analogy: O(n) is like a scorer reading every single ball of an innings once to find the highest-scoring over — you must check each one exactly once, so time grows directly with the number of balls bowled.
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) { /* single pass over n elements */
if (arr[i] > max) max = arr[i];
}
return max;
}O(n log n) — Linearithmic Time
This complexity typically arises from divide-and-conquer algorithms that split the input log n times and do O(n) work at each level, such as merge sort.
Cricket analogy: O(n log n) is like organizing a league table by repeatedly splitting groups of teams in half to rank them, then merging the sorted groups back together — just like merge sort splitting log n times and merging O(n) work each level.
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); /* recurse on left half */
mergeSort(arr, mid + 1, right); /* recurse on right half */
merge(arr, left, mid, right); /* O(n) merge at each of log n levels */
}
}O(n^2) — Quadratic Time
An O(n^2) algorithm typically has nested loops where each loop runs proportional to n, such as bubble sort or checking all pairs of elements.
Cricket analogy: O(n^2) is like comparing every player on a squad against every other player to rank head-to-head stats, a nested-loop check similar to bubble sort's repeated pairwise comparisons across the whole team.
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) { /* nested loop -> n * n work */
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}O(2^n) — Exponential Time
An O(2^n) algorithm's work doubles with every additional input element, commonly seen in naive recursive solutions like computing Fibonacci numbers without memoization.
Cricket analogy: O(2^n) is like a knockout prediction bracket where every extra match doubles the number of possible outcome paths to check, similar to naive recursive Fibonacci recomputing the same subproblems exponentially without memoization.
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); /* each call spawns 2 more calls -> O(2^n) */
}4. Example
#include <stdio.h>
int getFirstElement(int arr[], int n) { return arr[0]; }
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
int main(void) {
int arr[] = {4, 2, 9, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("O(1) first element: %d\n", getFirstElement(arr, n));
printf("O(n) max element: %d\n", findMax(arr, n));
return 0;
}5. Output
O(1) first element: 4
O(n) max element: 96. Key Takeaways
- Growth order from fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n).
- O(1): array indexing, hash table lookup (average case), pushing to a fixed-size stack.
- O(log n): binary search, balanced binary search tree operations.
- O(n): linear search, single-pass array traversal (sum, max, min).
- O(n log n): merge sort, quick sort (average case), heap sort.
- O(n^2): bubble sort, insertion sort, selection sort, naive nested-loop pair comparisons.
- O(2^n): naive recursive Fibonacci, generating all subsets of a set (power set).
Practice what you learned
1. Which of the following correctly orders complexity classes from fastest to slowest growth?
2. What is the time complexity of accessing arr[5] in a C array?
3. Why does the naive recursive Fibonacci function fib(n) = fib(n-1) + fib(n-2) have O(2^n) time complexity?
4. In Big-O analysis, why is an algorithm that performs 3n + 5 operations still classified as O(n)?
5. Which algorithm below is the classic example of O(n log n) time complexity?
Was this page helpful?
You May Also Like
Sorting Algorithms in C
Learn bubble sort in C step by step, with an overview of selection and insertion sort and correct time complexity analysis.
Recursion in C
Master recursion in C: base case, recursive case, call-stack tracing, factorial example, and avoiding stack overflow.
Binary Search in C
Learn binary search in C with syntax, a step-by-step explanation, working code, output, and O(log n) complexity analysis.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics