Time Complexity and Big O Notation
In this page:
What is Time Complexity
Time complexity is a way of describing how an algorithm's running time grows as its input size grows, without depending on the specific speed of the machine running it. It answers the practical question: if I double my input, does my program take roughly the same time, twice as long, or dramatically longer?
Example: What is Time Complexity
#include <iostream>
using namespace std;
int main() {
int n = 4;
int steps = 0;
for (int i = 0; i < n; i++) steps++;
cout << "n=" << n << " steps=" << steps << endl;
n = 8;
steps = 0;
for (int i = 0; i < n; i++) steps++;
cout << "n=" << n << " steps=" << steps << " (grows with n)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 4, steps = 0;
for (int i = 0; i < n; i++) steps++;
System.out.println("n=" + n + " steps=" + steps);
n = 8; steps = 0;
for (int i = 0; i < n; i++) steps++;
System.out.println("n=" + n + " steps=" + steps + " (grows with n)");
}
}for n in (4, 8):
steps = 0
for i in range(n):
steps += 1
print(f"n={n} steps={steps}")#include <stdio.h>
int main() {
int n = 4, steps = 0;
for (int i = 0; i < n; i++) steps++;
printf("n=%d steps=%d\n", n, steps);
n = 8; steps = 0;
for (int i = 0; i < n; i++) steps++;
printf("n=%d steps=%d (grows with n)\n", n, steps);
return 0;
}Login to try C/C++/Java code in the editor
Big O Notation
Big O notation gives an upper bound on that growth using the input size n, ignoring constant factors and lower-order terms because they matter less and less as n gets large. Writing an algorithm as O(n) or O(n log n) lets you compare very different pieces of code on equal footing.
Example: Big O Notation
#include <iostream>
using namespace std;
// O(n): time grows linearly with input size, ignoring constants.
int sumArray(int arr[], int n) {
int total = 0;
for (int i = 0; i < n; i++) total += arr[i];
return total;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
cout << "O(n) sum: " << sumArray(arr, 5) << endl;
return 0;
}public class Main {
// O(n): time grows linearly with input size, ignoring constants.
static int sumArray(int[] arr) {
int total = 0;
for (int x : arr) total += x;
return total;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println("O(n) sum: " + sumArray(arr));
}
}# O(n): time grows linearly with input size, ignoring constants.
def sum_array(arr):
total = 0
for x in arr:
total += x
return total
print("O(n) sum:", sum_array([1, 2, 3, 4, 5]))#include <stdio.h>
/* O(n): time grows linearly with input size, ignoring constants. */
int sumArray(int arr[], int n) {
int total = 0;
for (int i = 0; i < n; i++) total += arr[i];
return total;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
printf("O(n) sum: %d\n", sumArray(arr, 5));
return 0;
}Login to try C/C++/Java code in the editor
Common Complexities
O(1) constant time doesn't change with input size, like array indexing. O(log n) logarithmic time, like binary search, barely grows even for huge inputs. O(n) linear time scans everything once, and O(n²) quadratic time, common in naive nested loops, becomes painfully slow as n grows into the thousands.
Example: Common Complexities
#include <iostream>
using namespace std;
int main() {
int arr[] = {10, 20, 30, 40};
cout << "O(1) access arr[2]: " << arr[2] << endl;
int sum = 0;
for (int i = 0; i < 4; i++) sum += arr[i]; // O(n)
cout << "O(n) sum: " << sum << endl;
int pairs = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
pairs++; // O(n^2)
cout << "O(n^2) pairs counted: " << pairs << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40};
System.out.println("O(1) access arr[2]: " + arr[2]);
int sum = 0;
for (int i = 0; i < 4; i++) sum += arr[i];
System.out.println("O(n) sum: " + sum);
int pairs = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
pairs++;
System.out.println("O(n^2) pairs counted: " + pairs);
}
}arr = [10, 20, 30, 40]
print("O(1) access arr[2]:", arr[2])
total = sum(arr) # O(n)
print("O(n) sum:", total)
pairs = sum(1 for i in range(4) for j in range(4)) # O(n^2)
print("O(n^2) pairs counted:", pairs)#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40};
printf("O(1) access arr[2]: %d\n", arr[2]);
int sum = 0;
for (int i = 0; i < 4; i++) sum += arr[i];
printf("O(n) sum: %d\n", sum);
int pairs = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
pairs++;
printf("O(n^2) pairs counted: %d\n", pairs);
return 0;
}Login to try C/C++/Java code in the editor
Counting Operations
A practical way to estimate complexity without formal proofs is to count how many times the algorithm's main operation (a comparison, an addition, a loop iteration) runs relative to n. Nested loops over the same input size are a strong signal of O(n²) or worse.
Example: Counting Operations
#include <iostream>
using namespace std;
int main() {
int n = 4;
int comparisons = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
comparisons++;
cout << "n=" << n << " nested-loop comparisons=" << comparisons << " (n^2)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 4, comparisons = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
comparisons++;
System.out.println("n=" + n + " nested-loop comparisons=" + comparisons + " (n^2)");
}
}n = 4
comparisons = sum(1 for i in range(n) for j in range(n))
print(f"n={n} nested-loop comparisons={comparisons} (n^2)")#include <stdio.h>
int main() {
int n = 4, comparisons = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
comparisons++;
printf("n=%d nested-loop comparisons=%d (n^2)\n", n, comparisons);
return 0;
}Login to try C/C++/Java code in the editor
Why Complexity Matters
Complexity analysis matters because it predicts behavior on inputs you haven't tested yet. Two algorithms that both work correctly on a 10-element test case can behave completely differently on a million-element production dataset, and Big O is what tells you which one will hold up.
Example: Why Complexity Matters
#include <iostream>
using namespace std;
long linearSteps(int n) { return n; }
long quadraticSteps(int n) { return (long)n * n; }
int main() {
int n = 1000000;
cout << "O(n) steps: " << linearSteps(n) << endl;
cout << "O(n^2) steps: " << quadraticSteps(n) << " (much worse at scale)" << endl;
return 0;
}public class Main {
static long linearSteps(int n) { return n; }
static long quadraticSteps(int n) { return (long) n * n; }
public static void main(String[] args) {
int n = 1000000;
System.out.println("O(n) steps: " + linearSteps(n));
System.out.println("O(n^2) steps: " + quadraticSteps(n) + " (much worse at scale)");
}
}def linear_steps(n):
return n
def quadratic_steps(n):
return n * n
n = 1000000
print("O(n) steps:", linear_steps(n))
print("O(n^2) steps:", quadratic_steps(n), "(much worse at scale)")#include <stdio.h>
long linearSteps(int n) { return n; }
long quadraticSteps(int n) { return (long)n * n; }
int main() {
int n = 1000000;
printf("O(n) steps: %ld\n", linearSteps(n));
printf("O(n^2) steps: %ld (much worse at scale)\n", quadraticSteps(n));
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: