Ask Question
9 September, 10:58

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

+3
Answers (1)
  1. 9 September, 11:25
    0
    --> 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).
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Engineering if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers