Amortized complexity in layman’s terms?

by

Amortized complexity is the total expense per operation, evaluated over a sequence of operations.

The idea is to guarantee the total expense of the entire sequence, while permitting individual operations to be much more expensive than the amortized cost.

Example:
The behavior of C++ std::vector<>. When push_back() increases the vector size above its pre-allocated value, it doubles the allocated length.

So a single push_back() may take O(N) time to execute (as the contents of the array are copied to the new memory allocation).

However, because the size of the allocation was doubled, the next N-1 calls to push_back() will each take O(1) time to execute. So, the total of N operations will still take O(N) time; thereby giving push_back() an amortized cost of O(1) per operation.

Unless otherwise specified, amortized complexity is an asymptotic worst-case guarantee for any sequence of operations. This means:

  • Just as with non-amortized complexity, the big-O notation used for amortized complexity ignores both fixed initial overhead and constant performance factors. So, for the purpose of evaluating big-O amortized performance, you can generally assume that any sequence of amortized operations will be “long enough” to amortize away a fixed startup expense. Specifically, for the std::vector<> example, this is why you don’t need to worry about whether you will actually encounter N additional operations: the asymptotic nature of the analysis already assumes that you will.

  • Besides arbitrary length, amortized analysis doesn’t make assumptions about the sequence of operations whose cost you are measuring — it is a worst-case guarantee on any possible sequence of operations. No matter how badly the operations are chosen (say, by a malicious adversary!), an amortized analysis must guarantee that a long enough sequence of operations may not cost consistently more than the sum of their amortized costs. This is why (unless specifically mentioned as a qualifier) “probability” and “average case” are not relevant to amortized analysis — any more than they are to an ordinary worst-case big-O analysis!

More Related Contents:

  1. What is amortized analysis of algorithms? [closed]
  2. Find a pair of elements from an array whose sum equals a given number
  3. Find all paths between two graph nodes
  4. The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
  5. Sort points in clockwise order?
  6. How do you calculate the average of a set of circular data? [closed]
  7. Algorithm to check similarity of colors
  8. Why do we use Base64?
  9. Heap vs Binary Search Tree (BST)
  10. Finding maximum for every window of size k in an array
  11. Generate all unique substrings for given string
  12. Non-recursive depth first search algorithm [closed]
  13. How to Compute OBB of Multiple Curves?
  14. Calculating new longitude, latitude from old + n meters
  15. Largest circle inside a non-convex polygon
  16. How to check if line segment intersects a rectangle?
  17. How to compare two shapes?
  18. Probability of collision when using a 32 bit hash
  19. Generate a list of primes up to a certain number
  20. Algorithm to find multiple string matches
  21. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  22. Obfuscating an ID
  23. Algorithm for autocomplete?
  24. An inverse Fibonacci algorithm?
  25. Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
  26. How do ASCII art image conversion algorithms work? [closed]
  27. Reason for the number 5381 in the DJB hash function?
  28. What is the best way to check the strength of a password?
  29. What is the best algorithm for finding the closest color in an array to another color? [closed]
  30. What is the algorithm that opencv uses for finding contours?

Leave a Comment