The cost of amortized time complexity
Tags: array, datastructures, amotrizedtime, bigo
Published: 2020-05-09 23:48:29

---
title: The cost of amortized time complexity
published: true
description: In this article, we are going to explain the amortized time for algorithms.
tags: #array, #data structures, #amotrized time, #big O
---

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

![](https://beginnersbook.com/wp-content/uploads/2018/10/array.jpg)

#### 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](https://en.wikipedia.org/wiki/Big_O_notation)

### 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](https://en.wikipedia.org/wiki/Amortized_analysis)
2. [Cracking the coding interview](http://www.crackingthecodinginterview.com/)