alt Hacker NewsIsn't O(n - k) or O(len(l1) + len(l2)) just O(n)? Instead of blurring the line between complexity-analysis and cycle-counting, just print both the complexity and the est proportional cycle-count as separate measures.
Replies
srcreigh • yesterday at 8:48 PM
Well, yes, but if k is for example Ω(n) then O(n-k) is also O(1).
matheist • yesterday at 7:07 PM
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.
➕ show 1 reply
I think it's not unreasonable or uncommon for big O to track separate variables without reducing them, just to highlight the (lack of) sensitivity of different parameters.