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

- create a new array with double size of the old one.
- 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.

## Discussion