Finding amortized time complexity [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this 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.

Answer 2

When you insert N elements into the array, the array has to resize at each power of 4. The amount of time taken to resize at size 4^i is O(4^i). And similarly, the maximum resize is done at size N. So the total amount taken is:

T = 1 + 4 + 16 + ... + 4^x

where 4^x <= N. Thus T=O(4^x)=O(N). Thus the average time for each insert operation is on O(1).