Big-O notation VS. Amortized, Complexity Analysis
Tags: leetcode, algorithms, datastructures, interview
Published: 2024-03-03 16:53:39

   Hi everybody, my name is Michael Roks, I'm a backend software engineer at Yandex with 5+ YOE, and an hobbyist competitive programmer!

   Today we are going to talk about different ways to evaluate the Complexity of your algorithms, specifically - the Big-O Assymptotic Complexity VS. the Amortized complexity. Understanding this helps you get a better grasp on how the common data structures work inside, and it would be a plus for you to mention this in an interview :)

   Speaking in simple terms, the `Big-O` analysis is the "Worst possible" complexity of the algorithm - Time and/or Space complexity. And the `Amortized` analysis is the "Average amount of work for 1 run, if we run K times".

   For example, adding an element to a Dynamic Array is **O(n)** Time Complexity (I used the Big-O symbol `O` to denote the `Big-O - Worst-case-scenario Asymptotic analysis notation`), and **Amortized(1)** (There is no dedicated symbol for the amortized analysis, so I'm just putting the word `Amortized` in front of the complexity itself). 

   Why are the complexities like this?

   It's because of how the Dynamic Array handles adding and removing elements. Quick reminder - the dynamic array, in its most simple form, has the following methods:
1. Add to the end
2. Remove from end
3. Get by any index

   As well as the dynamic array has the underlying "regular" array & a `lastIndex` pointer to the place in that "regular" array, denoting the location of the last item.
When you are adding to the end of the array, there are 2 ways it can go:
1. You have spare space at the end of your "regular" array, you just write the provided element by `lastIndex`, and do `++lastIndex`.
2. You ran out of the spare space in the "regular" array, and now have to `expand`, and then append the provided element to the expanded array
A visual example!

![Using regular array in the Dynamic array, at some point we run out of available regular array and have to expand](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p1g3i672czl5zord10bg.png)

   In steps 2,3 & 4 we successfully added elements by `lastIndex` and moved it 1 to the right. But then we ran out of space & had to `Expand` the underlying regular array (create a new one greater in size &  copy all the existing elements into it). 

   As you can tell, the `Expand` operation is O(N) time complexity. As the `Expand` is eventually triggered by a single `add` operation, the `add` operation is also O(N), as O is the `Worst-case-scenario` notation. So adding to the dynamic array is **O(N)** operation.

   But next, let's look at how many expansions we have to do over K runs of `add`. In our example we started at size 3, and expand each time we fill up the dynamic array. Another visual example!

![Expanding dynamic array multiple times, it takes 2*K time on average](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y2151anjww7woue2cpjd.png)
   Here, we have to: 
1. Fill the initial array of size 3 (3 add operations), then expand (3 copy operations)
2. Finish filling the array of size 6 (another 3 add operations), then expand (6 copy operations)
3. Finish filling the array of size 12 (another 6 add operations), then expand (12 copy operations)
4. Finish filling the array of size 24 (another 12 add operations), then expand (24 copy operations)
5. Finish filling the array of size 48 (another 24 add operations), then expand (48 copy operations)
6. And so on…

   As you can see, continuing this series into the infinity, the total number of copy operations done because of K `.add` operations is ~2*K, so on average, adding an item to the end of a dynamic array requires 3 operations - 1 for adding & 2 for future expanding (as for K `.add` operations we require 3*K total amount of work)

   And this is exactly what Amortized analysis is - the average amount of operations for 1 run over K runs. And this is the proof, that adding to the end of a dynamic array is Amortized(1) Time Complexity. Thank you for you time & attention! Plz like & share if you thought this is a good read :D