Question

In special case, the time complexity of inserting/deleting elements at the end of dynamic array is __________

(a) O (n)

(b) O (n^1/2)

(c) O (log n)

(d) O (1)

Question is taken from Dynamic Array topic in division Arrays Types of Data Structures & Algorithms I

I have been asked this question during an interview.

Answer 1

Correct choice is (a) O (n)

To explain: In general, the time complexity of inserting or deleting elements at the end of dynamic array is O (1). Elements are added at reserved space of dynamic array. If this reserved space is exceeded, then the physical size of the dynamic array is reallocated and every element is copied from original array. This will take O(n) time to add new element at the end of the array.