The Amortized time complexity of increasing Array size

So how would we increase the size of an array?

Basic Approach: Whenever we need more space, increase it to the new required size. Example:
If the current array size is 4 and we want an array of size 5. Then we will create a new array of size 5 and copy all 4 elements in the new array.
Time Complexity will be O(n) //Copying old elements into a new array.
Amortized Time Complexity will also be O(n), as every time we need to copy all elements

credit: geeksforgeeks.org

What is the Amortized Time complexity of the above algorithm?

Credit: mnn.com

So in this way always half of the array will have 2 CPU cycles and will pay for the whole array in the worst-case scenarios where we need to copy the whole array.

In this way, the worst case time complexity is still O(n) which is equal to basic approach, but Amortized time complexity went straight to O(2){as we just need to give 2 CPU cycles for each operation} from O(n) of basic approach.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store