Big O of Common C++ Operations

Understanding the time complexity of common operations in C++ is crucial for writing efficient code. Here's a list of some common operations and their Big O complexities:

Accessing an Array Element by Index: $O(1)$

Accessing an element in an array by its index is a constant time operation, regardless of the size of the array.

1int array[10000];
2std::cout << array[0];// O(1)
3std::cout << array[9999];// Also O(1)

Inserting at the End of a Vector: $O(1)$ (on average)

In C++, a vector is a dynamic array that can grow in size. Inserting an element at the end of a vector is typically an $O(1)$ operation. However, if the vector needs to resize to accommodate the new element, it might need to copy all existing elements to a new memory location, which is an $O(n)$ operation. But this resizing happens infrequently (doubling each time), so the amortized (average over many insertions) time complexity is $O(1)$.

1std::vector<int> vec;
2vec.push_back(1);// O(1) on average

Inserting at the Beginning or Middle of a Vector: $O(n)$

Inserting an element at the beginning or middle of a vector requires shifting all the subsequent elements one position to the right, which is a linear operation.

1std::vector<int> vec {1, 2, 3, 4, 5};
2vec.insert(vec.begin(), 0);// O(n)

Searching for an Element in an Unsorted Array or Vector: $O(n)$

In the worst case, a search may need to check every element, resulting in linear complexity.

1int array[5] = {3, 1, 4, 1, 5};
2for (int i = 0; i < 5; i++) {
3  if (array[i] == 1) {// O(n)
4    std::cout << "Found";
5    break;
6  }
7}

Searching for an Element in a Sorted Array or Vector with Binary Search: $O(log n)$

If the array is sorted, we can use binary search, which has logarithmic complexity.

1std::vector<int> vec {1, 2, 3, 4, 5};
2bool found = std::binary_search(
3  vec.begin(), vec.end(), 3); // O(log n)

These are just a few examples. The C++ standard library provides many data structures and algorithms, each with its own time (and space) complexity guarantees. It's a good practice to familiarize yourself with these complexities to write efficient code.