What is Amortized Time Complexity Analysis
Tags: cpp, java, array, amortized
Published: 2023-12-07 06:27:41

---
title: What is Amortized Time Complexity Analysis
published: true
description: A case study of the ArrayList data structure and its amortized time complexity analysis.
tags: cpp, java, array, amortized
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9jnxnf6yaaugrx91totp.jpeg
# Use a ratio of 100:42 for best results.
# published_at: 2023-12-07 05:42 +0000
---

When designing and working with algorithms, our primary concern often revolves around the worst-case performance. This factor can significantly impact our application's overall performance.
However, there are instances when these worst-case time complexities might be somewhat deceiving.

<br>
<br>
<br>

Consider the example of a widely used data structure known as a **DynamicArray**. Specifically, in Java, we have the **ArrayList**, and in C++, the equivalent is the **vector** datatype – both exemplifying dynamic arrays. Dynamic Arrays are valuable because, under the hood, they store data sequentially, allowing for swift **sequential data access**. Despite this sequential storage, dynamic arrays perform dynamic resize operations when the capacity is reached, making things easier for us, because we do not have to worry about resizing the array ourselves, or memory allocations and deallocations. However, these operations come at a cost in terms of CPU cycles.

<hr>

###Analyzing the Worst Case Time Complexity of the Insert Operation for Dynamic Arrays

When scrutinizing the worst-case time complexity of an insert operation for dynamic arrays, it turns out to be **O(N + M)** where **N** is the number of elements inserted and **M** is the number of elements copied into a new memory buffer. This is due to the allocation of a new block of memory (typically double the size of the previous block), and copying all data from the old block to the new one. This doubling of memory and the subsequent copy operations are computationally expensive. Let's examine an example of how the insertion of eight elements would unfold in a dynamic array.

![An example of inserting 8 elements into a dynamic array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/djfchbanh62sxzhlswnd.png)


> If we can somewhat estimate the size requirements of our vector, reserving a block of memory during initialization can significantly improve the efficiency. This proactive approach minimizes the need for costly memory copy operations associated with resizing.

<i>back to the time complexity analysis...</i>


In this small example, the frequency of **O(1)** insert operations is considerably higher than the **O(N)+1** operations for memory copying to a new block. In situations where there is an imbalance in the frequency of different operations, with an expensive, infrequent operation occurring alongside a cheap, frequently occurring operation, it is better to perform an Amortized Performance Analysis to obtain a more accurate performance assessment.

<hr>

###Amortized Time Complexity Analysis

To comprehend the amortized time complexity, we need to properly account for the frequent **O(1)** insert operations alongside the infrequent but compute-intensive **O(N)+1** insert operations and divide the total cost of insertions over **N** insertions. This yields the average time complexity of the insert operation, which provides a more accurate representation than the pessimistic **O(N+M)** worst-case time complexity.


1. Assuming we insert **N** elements with constant insertion time, the time complexity for this operation would be **O(N)**.

1. Examining the above diagram of insert operations, we can observe that the doubling of the array operation takes place roughly **O(logN)** times.


Considering the above two facts, let's compute the amortized time complexity.

![Derivation of computing amortized time complexity of dynamicArray insert operation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ey2je6q5euf9pwbk351.png)


This result is powerful as it indicates that despite some operations being expensive (e.g., when resizing is required), the average cost of operations remains **constant** when spread out over a large number of operations.


In summary, Amortized Time Complexity Analysis emerges as a valuable tool for assessing algorithm performance. It excels in scenarios where frequent, low-cost operations coexist with occasional, compute-intensive ones. This analytical approach offers a nuanced understanding, allowing us to gauge performance more accurately and make informed decisions in algorithm design.

> Somewhere, something incredible is waiting to be known. - Carl Sagan