Difference between average case and amortized analysis

by

Average case analysis makes assumptions about the input that may not be met in certain cases. Therefore, if your input is not random, in the worst case the actual performace of an algorithm may be much slower than the average case.

Amortized analysis makes no such assumptions, but it considers the total performance of a sequence of operations instead of just one operation.

Dynamic array insertion provides a simple example of amortized analysis. One algorithm is to allocate a fixed size array, and as new elements are inserted, allocate a fixed size array of double the old length when necessary. In the worst case a insertion can require time proportional to the length of the entire list, so in the worst case insertion is an O(n) operation. However, you can guarantee that such a worst case is infrequent, so insertion is an O(1) operation using amortized analysis. Amortized analysis holds no matter what the input is.

More Related Contents:

  1. Why is the constant always dropped from big O analysis?
  2. Painter puzzle – estimation
  3. What is amortized analysis of algorithms? [closed]
  4. Painter puzzle – algorithmic estimation from first principles
  5. complexity in terms of big O
  6. Find a pair of elements from an array whose sum equals a given number
  7. Find all paths between two graph nodes
  8. find the only unpaired element in the array
  9. Sort points in clockwise order?
  10. How do you calculate the average of a set of circular data? [closed]
  11. Algorithm to check similarity of colors
  12. Why do we use Base64?
  13. Heap vs Binary Search Tree (BST)
  14. Generate all unique substrings for given string
  15. How to Compute OBB of Multiple Curves?
  16. Counting the adjacent swaps required to convert one permutation into another
  17. Calculating new longitude, latitude from old + n meters
  18. Largest circle inside a non-convex polygon
  19. How to check if line segment intersects a rectangle?
  20. How to compare two shapes?
  21. Generate a list of primes up to a certain number
  22. Best Fit Scheduling Algorithm
  23. Algorithm to find multiple string matches
  24. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  25. Finding how similar two strings are
  26. Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
  27. How can I perform Collision Detection on rotated rectangles? [closed]
  28. Find the pair across 2 arrays with kth largest sum
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment