3 ms·
Complexity measures the worst-case, not the amortized case. If you want to report proportional cycles for more fine-grained per-feedback, fine, report proportio
by mwkaufma 1mo ago
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.
- jeremyscanvic 1mo agoWorst 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.
- xigoi 1mo agoBig O notation has nothing to do with worst or best case. f = O(g) simply means that f is asymptotically bounded by a multiple of g.