Question

Many vectors are designed to double in size whenever a new element is inserted into a full vector. This operation may entail allocating a new array that is twice the size of the original, and then copying the original elements into the new array before appending the new element. Use one of the three methods taught in class to show that the push_back() operation of such a vector is amortized O(1).

Answer 1

Step-by-step explanation:

--> push_back() will insert the element given argument at the end of vector.

--> We will see amortized time taken for inserting n elements.

--> For inserting upto n/2 elements it takes O(1) time for each.

--> So, total time is O(n/2)

--> After that if we have to insert one more element, we have to allocate a new array that is twice the

size of the original, and then copying the original elements into the new array before appending the

new element.

--> Time Taken for this is O(1) for creating array and O(n/2) for copying.

--> Now, we can insert remaining n/2 elements in O(n/2).

--> So, total time is

T(n) = O(n/2) + O(1) + O(n/2) + O(n/2)

= O(3n/2 + 1)

= O(n)

--> Constants won't matter in Big-O notation.

--> So, for pushing 1 element by using push_back is O(1) because for n is O(n).