Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- They forgot to include GC overhead.by emil-lp
- how gc influence time complexity? elaborate, pksby feelamee
- Notable pitfalls:
- s[i:j] is O(j - i) because it creates a copy instead of a view
- max(range(n)) is O(n)
- substring search is O(n), which is good, but rfind is O(n m)
- iterative string concatenation (for c in ...: s += c) can be O(n^2) due to string immutability according to footnote 10, although it is O(n) in most cases due to an implementation detail of CPython: https://stackoverflow.com/a/34008199
by gpugreg - realloc is frequently O(n), ie CPython can avoid copying and immediately collecting the object but still copy the bytes. It's the same as calling reserve in a loopby speedstyle
- Note the footnote for rfind:
> This is the worst case. Reverse searches are O(n) on typical input.
by chronial - Nice page, but odd that they have O(...) in every row, surely that belongs in the column headerby jjgreen
- Isn'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.by mwkaufma
- Well, yes, but if k is for example Ω(n) then O(n-k) is also O(1).by srcreigh
- 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.
by matheist - If k = n - constant it comes out to O(1).by IsTom
- 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.
- Why are `min(r)` and `max(r)` for range objects o(n) ?
I thought min and max where constants stored in the object. Basically you are just asking for one of the parameters it was created with.
by wodenokoto - > Basically you are just asking for one of the parameters it was created with.
See, you already made a mistake:
4 is neither the min or max of the range (their actual names are start and stop), and notice how the max is the first argument and the min is the second argument>>> min(range(10, 1, -3)) 4Of course, the actual implementation of constant time min/max on range would be trivial.
by dist-epoch - Because the use case is very niche and nobody optimized it yet.
https://github.com/python/cpython/issues/135824#issuecomment...
`x in range(n)` is already optimized, but that was easier since the `__contains__` method already existed, but an equivalent `__min__` or `__max__` does not.
by gpugreg - Excellent. Previously this was only documented semi-unofficially on the wiki here: https://wiki.python.org/moin/TimeComplexityby Retr0id
- This was one of the main inspirations when I started https://pythoncomplexity.com/. Glad to see Big-O in the official docs. Maybe one day my project will become obsolete.
- Python is famously built around hash tables. So much so that several versions ago they made an improvement to the hash table implementation, and the entire language became several percent faster.
However, I'm surprised to see no data structures at all with O(log(N)) complexity. Surely there are some use cases for which that's desirable?
- One reason you don't see a data structure with O(log(n)) operations in this list is that priority queues/heaps are not a built-in type. Weirdly, there isn't a type for them at all, just a bunch of functions (good luck if you use them wrong). https://docs.python.org/3/library/heapq.htmlby krautsauer
- Dave Beazley has a great talk about using Python built ins [0] for data analysis and other quick operations.
As a meta note, I've used many of these builtins over the years but, due to LLMs, have been using them less and less. Re-watching the video almost felt like watching bushcrafters make a chair using just a knife and saw...
by alexpotato