the input size 𝑛 n increases.
In C++, you can see common Big O classes like 𝑂(1), 𝑂(log 𝑛), 𝑂(𝑛), 𝑂(𝑛 log 𝑛), and 𝑂(𝑛2) in simple code patterns and STL operations.
Common Big O classes with C++ examples
𝑂(1) – Constant time
The runtime does not depend on input size.
// Accessing an array element by index
int arr[1000];
int x = arr[5]; // O(1)
// Simple arithmetic / assignment
int y = a + b; // O(1)
bool equal = (a == b); // O(1)
// Push/back on vector (amortized)
std::vector v;
v.push_back(10); // amortized O(1) Typical 𝑂(1) patterns: single statements, no loops depending on 𝑛, direct index access, basic arithmetic.
𝑂(𝑛) – Linear time
Runtime grows proportionally with 𝑛 usually a single loop over all
elements.
// Sum of first n integers (loop version)
int sumOfNumbers(int n) {
int sum = 0;
for (int i = 1; i <= n; ++i) { // runs n times
sum += i; // O(1) work each time
}
return sum; // overall O(n)
}
// Linear search in an array
int linearSearch(const int arr[], int n, int target) {
for (int i = 0; i < n; ++i) { // up to n iterations
if (arr[i] == target)
return i;
}
return -1; // O(n)
}
// Traversing a vector
std::vector v = {1,2,3,4,5};
for (int x : v) { // n elements
std::cout << x << " "; // O(1) per element
} // total O(n) Patterns: one loop from 0 to 𝑛−1, iterating over a container once.
𝑂(log 𝑛) – Logarithmic time
Runtime grows with the number of times you can halve the problem; classic
example is binary search.
// Binary search on a sorted array (iterative)
int binarySearch(const int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) { // each step halves the range
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // O(log n)
}
Also common in C++ STL:
std::lower_bound, std::upper_bound, std::binary_search on sorted
ranges are 𝑂(log 𝑛).
𝑂 ( 𝑛 log 𝑛 ) – Linearithmic time
Typical for efficient sorting and some divide-and-conquer algorithms.
#include
#include
std::vector v = {5, 2, 9, 1, 5, 6};
std::sort(v.begin(), v.end()); // introsort: average O(n log n)Most comparison-based sorts in C++ (std::sort, std::stable_sort) are 𝑂 ( 𝑛 log 𝑛
) on average. 𝑂 ( 𝑛 2 ) – Quadratic time Usually nested loops
where both depend on 𝑛 n; common in naive sorting algorithms.
// Bubble sort (worst/average case)
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; ++i) { // ~n times
for (int j = 0; j < n - i - 1; ++j) { // ~n times
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]); // O(1)
}
}
} // total O(n2)
}
// Simple double loop example
for (int i = 0; i < n; ++i) { // n
for (int j = 0; j < n; ++j) { // n
std::cout << i << " " << j; // O(1)
} // n * n = O(n2)
}Also: worst-case of insertion sort and selection sort are
𝑂(𝑛2).
𝑂(2𝑛)– Exponential time
// Naive recursive Fibonacci
int fib(int n) {
if (n <= 1) return n; // base case O(1)
return fib(n - 1) + fib(n - 2); // each call branches into 2
} // roughly O(2n)Each increment of 𝑛 roughly doubles the number of calls.
Big O of common C++ STL operations
These are useful “real-world” examples when analyzing C++ code:
std::vector:
- operator[], at(): 𝑂 ( 1 )
- push_back: amortized 𝑂 ( 1 )
- insert/erase in the middle: 𝑂 ( 𝑛 )
std::vector: std::array:
- Index access: 𝑂 ( 1 )
std::list (doubly linked list):
- Insert/erase at known iterator: 𝑂 ( 1 )
- Traversal to find an element: 𝑂 ( 𝑛 )
std::unordered_set,std::unordered_map:
- Average insert/lookup/erase: 𝑂 ( 1 )
- Worst case (bad hash): 𝑂 ( 𝑛 )
std::set, std::map (balanced BST):
- Insert/lookup/erase: 𝑂 ( log 𝑛 )
std::sort, std::stable_sort:
- Average: 𝑂 ( 𝑛 log 𝑛 )
-
Worst case for
<std::sort: >typically 𝑂 ( 𝑛 log 𝑛 ) with
introsort
Practical Big O Examples in C++
Presenting Few Simple Examples in C++ for Big O Notation
| Complexity | Example | Evaluation |
|---|---|---|
| O(1) | Addition of a + b | A fixed number of operations regardless of input size |
| O(n) | Loop from 0 to n-1 | Loop executes n times |
| O(log n) | Binary search | Search space is roughly halved each iteration |
| O(n²) | Two nested loops | n × n = n² iterations |
| O(n³) | Three nested loops | n × n × n = n³ iterations |
| O(2ⁿ) | Naive recursive Fibonacci | More precisely, its running time is O(φⁿ), often simplified to O(2ⁿ) |
| O(n!) | Recursive factorial | The recursive factorial is O(n), not O(n!) |
Evaluation
1. O(1) — Constant
cin >> a >> b;
cout << a + b; There is a fixed amount of work, so:
Time = O(1)
Even if the values of a and b are very large, the number of program steps doesn’t depend on n.
2. O(n) — Linear
for (int i = 0; i < n; ++i) {
cout << i << " ";
} The loop executes n times.
Time = O(n)
3. O(log n) — Logarithmic
The binary search is a good example:
while (left <= right) {
int mid = left + (right - left) / 2;
...
} Every iteration eliminates approximately half of the remaining elements.
For example:
1000 → 500 → 250 → 125 → … → 1
So:
Time = O(log n)
One minor issue: your array contains only 7 elements, so technically that particular program has a fixed-size input and could be viewed as O(1). To demonstrate O(log n) properly, use an array whose size depends on n.
4. O(n²) — Quadratic
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
...
}
} The inner loop runs n times for every one of the n outer iterations:
n × n = n²
Therefore:
Time = O(n²)
5. O(n³) — Cubic
You have three nested loops:
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
That’s:
n × n × n = n³
Therefore:
Time = O(n³)
6. O(2ⁿ) — Exponential
The Fibonacci example – A simple recursive algorithm that makes two recursive calls at each level:
#include
using namespace std;
int fibonacci(int n) { if (n <= 1) { return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main(){ int n;
cin >> n;
cout << "Fibonacci of " << n << " is: "
<< fibonacci(n) << endl;
cout << "This is O(2^n) - Exponential Complexity";
O(2ⁿ) Commonly used simplified bound for this basic Big O Examples in C++
7. O(n!) — Factorial
To actually demonstrate O(n!), generate all permutations of n elements:
#include
#include #include
using namespace std; void generatePermutations(vector& arr, int index) {
if (index == arr.size()) {
for (int x : arr) {
cout << x << " ";
}
cout << endl;
return; }
for (int i = index; i < arr.size(); ++i){
swap(arr[index], arr[i]);
generatePermutations(arr, index + 1);
swap(arr[index], arr[i]);
}
}
int main() {
int n;
cin >> n;
vector arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = i + 1;
}
generatePermutations(arr, 0);
cout << "This is O(n!) - Factorial Complexity";
return 0;
}
For n elements, there are:
n! = n × (n-1) × (n-2) × … × 1
permutations.
So the algorithm has O(n!) time complexity (ignoring the additional O(n) work needed to print each permutation).
