The cost of amortized time complexity

Amortized Time Complexity, worst case happens every once in a while.

I'm so tired of searching for good resources that discussing amortized time complexity, so what is the meaning of amortized time?

first thing let's define the meaning for the array, and why we need it?

Array

In computer science, an array data structure or simply an array is a data structure that consisting of a collection of elements values or variables.

let's simplify it, an array is a data structure that can contain multiple values, we can think of it as a list of multiple things.

an array is a contiguous block of memory, let's imagine that we have an array of size 5, so it will reserve 5 blocks (block after block) in the memory, so memory will always have a fixed size.

How programming languages solve the fixed-size problem to give us the ability to create a dynamical size array.

Many programming languages solve this problem by creating an ArrayList or Dynamically resizing array.

What is array list?

is a data structure that allows us to have the benefits of an array while offering flexibility in size, you won't run out of space since in the Array List will grow as you insert elements.

The Array List is implemented with an array as the hurt of its logic when the array hits capacity, the Array List will create a new array with double the capacity and copy all the elements over the new area.

Whaaaaaat, what did you said ??

Yeh, it is doing 2 operations:

1. create a new array with double size of the old one.
2. copy all elements over to the new array.

as we know that when we insert new value at the end of the array, it is required a single operation with constant time complexity O(1), Please check this link, if you don't know, how to describe your runtime Big O noation

So, What is the runtime (complexity) of the insertion?

let's explain how it works?, the array could be full, if the array contains N elements then inserting new element will take O(n) time because we have to create a new array of size 2*N and then copy N elements over the new array.

we know that it doesn't happen very often, the vast majority of the time insertion will be O(1).

So, what is amortized time does?

Amortized time allows us to describe these cases, cases that happen every once in a while, and won't happen again for a while.

In case that we discussed, the amortized time is:

when we insert a new element, the first thing we are going to double the array capacity the double-takes respectively 1, 2, 4, 8, 16, 32, 64, X, so what we mean by the sum of this equation? this is roughly 2X.

Therefore, X insertion takes O(2X). the amortized time for each insertion is O(1), so we are not saying it O(1) time complexity, it is amortized O(1) time complexity.

Summary

Amortized time describes cases that happen every once in a while, and won't happen again for a while.

resources

1. Amortized time
2. Cracking the coding interview