# The Amortized time complexity of increasing Array size

Feel free to checkout this blog to see increasing array size in action.

Firstly what is Amortized time complexity?

According to Wikipedia: In computer science, amortized analysis is a method for analyzing a given algorithm’s complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic.

In simple words: Instead of calculating time complexity of an algorithm based on its worst case operation, we calculate amortized time complexity of an algorithm by calculating average time taken by all operations.

## 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

Better Approach: Let's understand another algorithm for increasing the array size: Whenever we will face an overflow we will increase size of the array to the double of original size.

Now, if you see when we are trying to insert 5, we have created a new array of size 8 and copied the previous 4 elements and then inserted 5.

The Time Complexity of this algorithm is also O(n) where n is the number of elements in the array. As, In the worst case(at the time of inserting 5) we are copying all the 4 elements in the new array.

Let’s consider that each copy of an element will cost us 1 CPU cycle. When we are calculating the time complexity we see the worst case of the algorithm, it will be when we are trying to insert the 5th element as we are increasing array size to 8 and copying all the elements in the new array. This will cost us 4 CPU cycles. So to perform the operation of inserting 5 in the array we will require 4 CPU cycles to perform that operation.