4 ms·

> Expected time refers to a single operation. Amortized time describes the mean time of a series of operations. Pardon my ignorance but I don't see the differe

> Expected time refers to a single operation. Amortized time describes the mean time of a series of operations. Pardon my ignorance but I don't see the difference between these two sentences. Expected time of a single operation = Sum of time taken for all possible input cases / Number of cases (assuming each input case is equally likely to occur). Is it not? Isn't it then the same as amortized time?

vient 4y ago
A difference is in the number of times you use some operation. For example, you expect to do a lot of pushes in vector so you can say about amortized time because it will hold on average and you can calculate running time from it and expected number of pushes somewhat precisely (with unknown constant multiplier which is independent of input data, on theoretical hardware at least). On the other hand, an individual array is usually sorted only once. Here it is more appropriate to speak about average or expected complexity of quicksort which is O(NlogN) but in you particular run it may become either better or worse and this will noticeably affect running time, by a factor dependent of N value. You can say about amortized time of quicksort though if you expect to sort different arrays a lot of times and you know their distribution, or at least the fact that they are sufficiently random shuffled or maybe sufficiently sorted beforehand.
- ctrlmeta 4y ago
  Ah! Finally it clicked! Thanks for the nice example in your comment.
aliceryhl 4y ago
They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call the same operation multiple times (it has nothing to do with randomness). Hash maps provide O(1) expected lookups. This running time relies on randomness, and it is the average running time of one operation. If you are very unlucky (or if an attacker can predict your random number generator), then it is possible for every single lookup to run in O(n) time. Dynamic arrays (vector in C++, ArrayList in Java) provide O(1) amortized push calls. Dynamic arrays sometimes have to copy every element in the array into a new allocation when you call push. However, by doubling the size every time this happens, the copies happen so rarely that if you push k times (starting with an empty array), then the total running time of all k calls is O(k), even though a small number of the calls are much more expensive than O(1). So, unlike expected running times, an amortized running time of O(f(n)) is an absolute guarantee that calling it k times in a row never runs slower than O(k*f(n)).

vient 4y ago

A difference is in the number of times you use some operation. For example, you expect to do a lot of pushes in vector so you can say about amortized time because it will hold on average and you can calculate running time from it and expected number of pushes somewhat precisely (with unknown constant multiplier which is independent of input data, on theoretical hardware at least). On the other hand, an individual array is usually sorted only once. Here it is more appropriate to speak about average or expected complexity of quicksort which is O(NlogN) but in you particular run it may become either better or worse and this will noticeably affect running time, by a factor dependent of N value. You can say about amortized time of quicksort though if you expect to sort different arrays a lot of times and you know their distribution, or at least the fact that they are sufficiently random shuffled or maybe sufficiently sorted beforehand.

ctrlmeta 4y ago
Ah! Finally it clicked! Thanks for the nice example in your comment.

aliceryhl 4y ago

They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call the same operation multiple times (it has nothing to do with randomness). Hash maps provide O(1) expected lookups. This running time relies on randomness, and it is the average running time of one operation. If you are very unlucky (or if an attacker can predict your random number generator), then it is possible for every single lookup to run in O(n) time. Dynamic arrays (vector in C++, ArrayList in Java) provide O(1) amortized push calls. Dynamic arrays sometimes have to copy every element in the array into a new allocation when you call push. However, by doubling the size every time this happens, the copies happen so rarely that if you push k times (starting with an empty array), then the total running time of all k calls is O(k), even though a small number of the calls are much more expensive than O(1). So, unlike expected running times, an amortized running time of O(f(n)) is an absolute guarantee that calling it k times in a row never runs slower than O(k*f(n)).