alt Hacker NewsComplexity measures the worst-case, not the amortized case. If you want to report proportional cycles for more fine-grained per-feedback, fine, report proportional-cycles, but that's not Big-O, so don't use that notation.
Complexity measures the worst-case, not the amortized case. If you want to report proportional cycles for more fine-grained per-feedback, fine, report proportional-cycles, but that's not Big-O, so don't use that notation.
Worst case can mean two things. For fixed n, worst list content and worst k, which gives you the less fine-grained O(n). For fixed n and fixed k, worst list content, which gives you the fine-grained O(n - k).
Edit: Another example of that is the complexity of convolutional filtering, which is O(n min(log n, k)) for a signal of length n and a kernel of size k.