4 ms·
Saying that l.pop(k) has time complexity O(n-k) implies that popping something at position 5 from the end has bounded (amortized) time cost regardless of the le
by matheist 1mo ago
Saying that l.pop(k) has time complexity O(n-k) implies that popping something at position 5 from the end has bounded (amortized) time cost regardless of the length of the list l, ie even if we let the list grow arbitrarily.
It's a stronger claim than just saying O(n), because in the latter case you wouldn't be able to conclude that popping something 5 from the end has bounded time as the list grows.
- mwkaufma 1mo agoComplexity 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.