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?

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.

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)$ (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)$.

std::vector<int> vec;
vec.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.

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)$

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(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.

This Question is from the Lesson:

### Algorithm Analysis and Big O Notation

An introduction to algorithms - the foundations of computer science. Learn how to design, analyze, and compare them.

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

This Question is from the Lesson:

### Algorithm Analysis and Big O Notation

An introduction to algorithms - the foundations of computer science. Learn how to design, analyze, and compare them.

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.