Amortized Time Complexity in Data Structures

Example of Amortized Analysis on Dynamic Array

This section will discuss the example of amortized time complexity in Data structure.

Suppose we have to store elements and we don’t know the number of elements in advance. So, we can use a dynamic array to store the elements. If we declare a large size of the array initially, then we have to compromise with the space complexity. So, we start with a zero-size dynamic array and start inserting elements. Whenever a new element comes, and we have a vacant space in the array, it takes O(1) time to insert a new element into the array. But whenever there is not a vacant space in the array, the size of the array is doubled. So, if there is no vacant space in the array at the time of nth element insertion, it takes O(n) time for inserting that element into the dynamic array.

This kind of dynamic array is implemented using ArrayList in Java and vectors in C++.

See the figure below for a better understanding of amortized time complexity in data structures:

Here, we can observe that when (n-1) is a power of 2, we come to a case when we don’t have a vacant space in the dynamic array and we need to double its size to accommodate the new element. In this case, the time complexity is O(n), else the time complexity to insert the new element is O(1).

The amortized cost of insertion:

Read More - Time Complexity of Sorting Algorithms and  Euclid GCD Algorithm

Conclusion

This article discussed the concept of “Amortized time complexity in Data Structures.”

Also read - Data Structure MCQ

If you want to solve problems on data structures and algorithms for practice, you can visit Code360.

You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.