Simple Vector (Amortized) Big-O and Timing video (37 minutes)
push_back big-O
In our push_back code, we only have to create a new array and copy things when the array is full. Even though a single call to push_back is O(n) because it will do O(n) copies, in the worst case, push_back is not always that bad. What's the big-O of calling push_back O(n) times?
To find out, let's look at how many copies are done when we run out of capacity. We know that since we're doubling the array each time, we first resize after 2 elements, 3 elements, 5 elements, 9 elements, 17 elements, 2^k + 1 elements, etc. Here we'll create a table showing the number of elements inserted and count up the number of copies that we have to do per resize and in the last column, we'll sum up the total number of copies done so far:
| size=n (smallest) | size=n (biggest) | capacity | copies to resize | total copies |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 2 | 2 | 2 | 1 | 1 |
| 3 | 4 | 4 | 2 | 3 |
| 5 | 8 | 8 | 4 | 7 |
| 9 | 16 | 16 | 8 | 15 |
| 17 | 32 | 32 | 16 | 31 |
| 33 | 64 | 64 | 32 | 63 |
| 65 | 128 | 128 | 64 | 127 |
| 129 | 256 | 256 | 128 | 255 |
| 2^(k - 1) + 1 | 2^k | 2^k | 2^(k - 1) | 2^k - 1 |
| n | 2n - 2 | 2n - 2 | n - 1 | 2n - 2 |
The number of copies we have to do is O(n) for single push_back because we might have to copy the n elements we've inserted so far... but it's also O(n) to call push_back n times. So, if you divide the big-O of doing the operation n times by n, we get that push_back is amortized O(n) / n = O(1).
Timing It
Let's see if the theory holds up. Here we'll add an ops_counter to our TemplateVector::push_back to see if it actually scales like we expect and we'll run a timer to see the actual time and plot them both on a graph to see how the real running time lines up with all the operations we're counting.
#pragma once
template <typename T>
class TemplateVector {
int capacity, size_;
T* values;
public:
int ops_counter;
TemplateVector() : capacity(1), size_(0), ops_counter(0) {
values = new T[capacity];
}
~TemplateVector() {
delete[] values;
}
void push_back(const T& value) {
++ops_counter;
if (size_ >= capacity) {
// Create a new bigger
ops_counter += 2 * capacity + 3;
const int new_capacity = 2 * capacity;
T *new_lines = new T[new_capacity];
// Copy everything to the big array
for (int i = 0; i < size_; ++i) {
++ops_counter;
new_lines[i] = values[i];
}
// Delete old array
ops_counter += capacity;
delete[] values;
// Make lines point to new array
ops_counter += 2;
values = new_lines;
capacity = new_capacity;
}
++ops_counter;
values[size_] = value;
++ops_counter;
++size_;
}
T* begin() {
return values; // same as &strs[0]
}
T* end() {
return values + size_; // same as &strs[size]
}
T& operator[](int index) {
return values[index];
}
int size() {
return size_;
}
};#include <iostream> // std::cout, std::endl
#include <chrono>
#include <vector>
#include "template_vector.h"
using namespace std;
class SimpleTimer {
std::chrono::time_point<std::chrono::steady_clock> start_time;
public:
void start() {
start_time = std::chrono::steady_clock::now();
}
// Return the number of seconds since .start() was called
double elapsed_seconds() const {
std::chrono::duration<double> diff(std::chrono::steady_clock::now() - start_time);
return diff.count();
}
};
int main(int argc, const char *argv[]) {
TemplateVector<int> vec;
SimpleTimer timer;
cout << "n,ops_counter,elapsed_seconds" << endl;
timer.start();
for (int i = 0; i < 100000; ++i) {
vec.push_back(i);
// Only print out one in every thousand lines so the output isn't huge
if (i % 1000 == 0) {
cout
<< vec.size() << "," << vec.ops_counter << ","
<< timer.elapsed_seconds() << endl;
}
}
return 0;
}$ clang++ -pedantic -Wall -lm -std=c++20 -o vector_demo vector_demo.cpp
$ ./vector_demo
n,ops_counter,elapsed_seconds 1,3,2.165e-06 1001,7145,3.3783e-05 2001,14246,4.8461e-05 3001,25443,6.8396e-05 4001,28443,7.7585e-05 5001,47832,0.000104969 6001,50832,0.000115297 7001,53832,0.000124963 8001,56832,0.000133376 9001,92605,0.000174228 10001,95605,0.000184166 11001,98605,0.000193899 12001,101605,0.000203507 13001,104605,0.000213172 14001,107605,0.000223502 15001,110605,0.000233587 16001,113605,0.000241948 17001,182146,0.000316842 18001,185146,0.000327456 19001,188146,0.000337097 20001,191146,0.000346664 21001,194146,0.000356375 22001,197146,0.000366376 23001,200146,0.000376393 24001,203146,0.000386423 25001,206146,0.00039641 26001,209146,0.000406512 27001,212146,0.000416429 28001,215146,0.000426799 29001,218146,0.000436859 30001,221146,0.00044701 31001,224146,0.00045712 32001,227146,0.000468376 33001,361223,0.000616044 34001,364223,0.000627065 35001,367223,0.000636935 36001,370223,0.000646894 37001,373223,0.000656967 38001,376223,0.000666838 39001,379223,0.00067669 40001,382223,0.000686604 41001,385223,0.000696464 42001,388223,0.000706336 43001,391223,0.000715307 44001,394223,0.000725165 45001,397223,0.000735013 46001,400223,0.000744809 47001,403223,0.000754726 48001,406223,0.00076464 49001,409223,0.000775671 50001,412223,0.000785564 51001,415223,0.000795493 52001,418223,0.000805426 53001,421223,0.000815395 54001,424223,0.000826147 55001,427223,0.000836084 56001,430223,0.000846094 57001,433223,0.000855625 58001,436223,0.000865761 59001,439223,0.000889067 60001,442223,0.000902478 61001,445223,0.000915648 62001,448223,0.000926382 63001,451223,0.000935354 64001,454223,0.000945244 65001,457223,0.00095407 66001,722372,0.00118968 67001,725372,0.00120958 68001,728372,0.00121967 69001,731372,0.00122884 70001,734372,0.00123783 71001,737372,0.00124671 72001,740372,0.00125567 73001,743372,0.00126459 74001,746372,0.00127358 75001,749372,0.00128242 76001,752372,0.00129131 77001,755372,0.00130019 78001,758372,0.0013091 79001,761372,0.00131801 80001,764372,0.00132702 81001,767372,0.00133692 82001,770372,0.00134581 83001,773372,0.00135473 84001,776372,0.00136365 85001,779372,0.00137249 86001,782372,0.00138004 87001,785372,0.00138897 88001,788372,0.00139821 89001,791372,0.00140708 90001,794372,0.00141592 91001,797372,0.00142601 92001,800372,0.00143494 93001,803372,0.00144352 94001,806372,0.00145244 95001,809372,0.00146106 96001,812372,0.00147003 97001,815372,0.00147988 98001,818372,0.00148884 99001,821372,0.00149787
