Algorithm Analysis and Big O Notation

Big O of Common C++ Operations

What is the time complexity of common C++ operations like accessing an array element or inserting into a vector?

Abstract art representing computer programming

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)O(1)

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

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

Inserting at the End of a Vector: O(1)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)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)O(n) operation. But this resizing happens infrequently (doubling each time), so the amortized (average over many insertions) time complexity is O(1)O(1).

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

Inserting at the Beginning or Middle of a Vector: O(n)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.

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

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

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

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

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

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

std::vector<int> vec {1, 2, 3, 4, 5};
bool found = std::binary_search(
  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.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved