Finding amortized time complexity

Question

So I wrote a function push_back for a vector class, and I'm now trying to figure out the amortized time complexity. I'm pretty new to the theoretical side of programming, so if someone could walk me through it that would be amazing.

This is my function:

void Vector<T>::push_back(const T &e) {
    if(vsize + 1 > capacity)
        allocate_new();
    array[vsize] = e;
    vsize++;
}

and this is my allocate_new function:

void Vector<T>::allocate_new() {
    capacity = vsize * 4;
    T* tmp = new T[capacity];

    for(int i = 0; i < vsize; i++)
        tmp[i] = array[i];

    delete[] array;
    array = tmp;
}

Answer 1

The short answer is that as the storage gets larger, a copy takes 4 times as long, but happens only 1/4^th as often. The 4 and 1/4^th cancel so you end up with (amortized) constant time.

Ignoring the precise factor you've chosen, in the long term you get O(N * 1/N) = O(1) -> amortized constant time.