Amortized Analysis - Dummies Overview

Introduction

 "Amortized!!! what the hell is that?" - is the first voice i would hear from any dummy like me. :) But when it comes to algorithms, performance matters. Algorithm is not something we write daily, (write and throw away code). That's the reason why along with algorithms, mathematics becomes a must. But with modern software engineering/agile ways of programming, mathematics is hidden in the form of requirements.

  Amortized - in my term means, paying your home loan using EMI option for life long. :) But the EMI balance reduces in long run as i pay up my interest first. It's is also associated with depreciation in general terms.
 

  But why would depreciation related to algorithms?

Concept

   Faster depreciation, we generally don't consider that product if it has a huge price tag. In algorithms terms, huge price tag (cost) is a big no no as we all know. But at the same it, algorithms require faster depreciation. That is, the cost should reduce when input size increases. How is that possible!!?? Who would need a product even though it costs less with faster depreciation? There are still people who buy made in china products. ;)

  

  Just Kidding.. Faster depreciation is not possible but at least there should be some balanced depreciation with the size of data an algorithm is processing. This is where we come with Big-Oh, Small-Oh, Smallest-Oh.. all that stuff!! :P

  But why that 'O'? There are many other letters in English. It's just the function naming similar to f(x) in mathematics. There are other functions as small-O, big/small-theta, big/small-gama for average/best cases. We use 'O' for indicating the worst case

More concepts

    Amortized analysis gives as ways to calculate like a banker, the cost involved in an algorithm by running through each and every line in code. The various ways to calculate are clearly given in many sites: the aggregate method, the accounting method, and the potential method (http://en.wikipedia.org/wiki/Amortized_analysis). Usually, algorithm designers use the above methods to optimize the algorithm for a longer run with huge data sets.

  More to come from scratch about algorithms.