For instance, suppose I have an algorithm that's O(n) and an algorithm that's an amortized O(n). Is it fair to say that in strictly big oh terms, the non-amortized algorithm will always be as fast or faster than the amortized algorithm? Or is there ever any reason to prefer the amortized version (ignoring things like code simplicity or ease of implementation)?
+5
A:
Or is there ever any reason to prefer the amortized version
Smaller constants.
Anon.
2010-02-22 01:36:43
Also, as in the case of a dynamic array, you can get more efficient storage for equivalent amortized runtime.
Michael Aaron Safyan
2010-02-22 04:49:47
+1
A:
Big O notation tells you about how your algorithm changes with growing input. It is not a shortcut for profiling your code.
It is possible that a better algorithm is O(n^2) for all n in your program, because there is a constant in an O(n) that is larger.
So your choice of algorithms really depends on which algorithm is faster for your input size. I guess the answer to your question is to profile both algorithms in your program and then decide which is faster.
Brian R. Bondy
2010-02-22 01:37:39
I'm fully aware of the limitations of big o. I would just like to know if there's any difference from a theoretical standpoint.
Jason Baker
2010-02-22 02:02:01
+7
A:
- Big O notation only tells you how your code scales, not how fast it will be for finite N.
- The difference between amortized and non-amortized is important if you care about worst-case performance or latency (such as real-time or interactive systems). If you only care about average throughput, though, they're for all practical purposes the same. Amortized analysis is good enough even in some very performance-critical situations like scientific computing and large-scale data mining.
dsimcha
2010-02-22 01:51:24
I disagree with your number 1. big O only tells you how the worst possible scenario scales. What you are describing is actually an upper and lower bound, not just an upper bound.
San Jacinto
2010-02-22 02:16:37
@San Jacinto, big-Oh notation simply indicates that it is an asymptotic upper-bound. Big-Oh may be used to give an upper-bound on the "worst-case" as well as the "average-case" (it can even be used for the "best-case", although that is generally less useful).
Michael Aaron Safyan
2010-02-22 04:52:14
@michael I have a perfect understanding of big O. I wasn't disagreeing with the math definition but rather dsimcha's definition.
San Jacinto
2010-02-22 13:36:05
+1
A:
A classic example of the need for amortized algorithm would be std::vector for which insert is amortized O(1).
Some reasons to use amortized algorithms:
- Much more efficient average case.
- Easier Implementation.
- No worst case guarantee algorithm exists.
Moron
2010-02-22 01:51:42
So does that mean that there's no difference from a strictly big o point of view?
Jason Baker
2010-02-22 02:03:03
Yes, there is a difference. "From a strictly big-o" point of view must consider worst case running time in ALL cases.
Billy ONeal
2010-02-22 02:08:15
From big O point of view n = 10000000*n. So yes, it does not make a difference. From a _behavior_ point of view they are different. An O(n) algorithm guarantees O(n) _for any_ input instance. Amortized gives no such guarantees. The O(n) guarantee is usually averaged over a sequence/set of input (like std::vector).
Moron
2010-02-22 02:13:17
+2
A:
The main difference between a O(n) algorithm and an amortized O(n) algorithm is that you don't know anything about the worst-case behavior of the amortized O(n) algorithm. In practice, that doesn't matter very often: If your algorithm is being run many times, then you can count on the law of averages to balance out a few bad cases, and if your algorithm isn't being run very many times, then it's unlikely that you'll ever hit the worst case at all.
The only cases where the word "amortized" should matter are cases where you can't accept occasional bad performance for some reason. For example, in GUI applications, you would happily give up some average-case performance in return for a guarantee that you'll never bog down and stop responding while the user is sitting there and getting bored. In such applications, you want to make sure that even the worst-case behavior is good for any code that could cause the GUI to stop responding.
Still, most of the time, you don't need to worry about amortized O(n) versus O(n), and you can worry instead about what the constant factors are (as others have already said).
Joe Carnahan
2010-02-22 02:05:58
By definition you have knowledge of the worst-case behavior of an amortized algorithm. That's how you amortize it!
San Jacinto
2010-02-22 02:18:39
True, assuming that you're the one who performed the analysis and computed the amortized cost. However, if someone just tells you "This operation is amortized O(_)" and provides no other information, then you don't know what the worst case cost is.
Joe Carnahan
2010-02-22 03:17:54
@San Jacinto, it depends on how you define "worst case". Is that worst for all n taken as a whole, or worst for a single operation? Big-O tells you nothing about the worst case for a single operation, and "amortized" implies that there will be large variability.
Mark Ransom
2010-03-01 23:45:22
A:
Strictly speaking big-O isn't precise enough of a measure to so be able to say that an algorithm with O(n) is faster than one with a amortized O(n). Think about it. If you drop down a level of fidelity in your complexity analysis, the constant factors may be significantly different and make the amortized version faster.
Also, the impact of amortization tends to depend on use. For example, if you're using a hash table, the impact of the amortization will be largely dependent on your ratio of get to add operations. So if you add 1000 entries, then do a billion lookups, the fact that you had to rehash a couple times doesn't make much of a difference. But if you're constantly adding entries the cost of rehashing might add up.
That's why amortization is different than worst case. Big-O reflects the worst case, while amortization lets you say "one in every x will take a hit, and x is sufficiently large that it doesn't matter." Also, if you consider examples like insertion into a hash table, x grows according to some constant. So if you have a hash table that starts with 100 buckets and doubles every rehash, then the rehashes are asymptotically going to get farther and farther apart. In addition, the absolute worst case complexity for an algorithm with an amortized complexity is dependent on previous calls, while in measures like average case the calls are considered independent.
Erik Engbrecht
2010-02-22 02:48:03