Skip to content

Add a page detailing the time complexity of operations on built-in types #154363

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
StanFromIreland merged 18 commits into from
Aug 24, 2026
Merged

Add a page detailing the time complexity of operations on built-in types #154363

Changes from 1 commit
Commits
Show all changes
18 commits
Select commit Hold shift + click to select a range
80088bf
Add a 'Time complexity of operations on built-in types' section
StanFromIreland Jul 8, 2026
84b95f9
Ned's suggestion for blog post rec.
StanFromIreland Jul 8, 2026
1982202
Revert that
StanFromIreland Jul 21, 2026
64fb553
Little fixups
StanFromIreland Jul 21, 2026
0392d7e
Apply review suggestions from Pieter and Bénédikt
StanFromIreland Jul 21, 2026
9e1a82a
Address Pieter's very helpful review
StanFromIreland Aug 6, 2026
f19c249
Merge branch 'main' into timecomplexity-doc
StanFromIreland Aug 10, 2026
d0ca44c
Simplify complexity notation addressing part of Serhiy's comments
StanFromIreland Aug 11, 2026
7e297d6
Carol's suggestion
StanFromIreland Aug 12, 2026
22d5586
Ned's review
StanFromIreland Aug 13, 2026
5f21510
Missed a few, oops!
StanFromIreland Aug 13, 2026
29e2017
Ned's review
StanFromIreland Aug 13, 2026
4d223f1
Address @dg-pb's review re. reverse string search complexity
StanFromIreland Aug 13, 2026
a893080
Try to simplify footnote
StanFromIreland Aug 13, 2026
c4a75fd
Remove note
StanFromIreland Aug 20, 2026
eac04b8
Drop "very"
StanFromIreland Aug 22, 2026
27e9cd6
Address Bénédikt's review
StanFromIreland Aug 23, 2026
116f21e
Switch back to `l`
StanFromIreland Aug 23, 2026
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Missed a few, oops!
  • Loading branch information
@StanFromIreland
StanFromIreland committed Aug 13, 2026
commit 5f215109a316472719399f50c50a2fb578347586
24 changes: 12 additions & 12 deletions Doc/library/time-complexity.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -165,18 +165,18 @@ the same costs.
- *O*\ (1)
* - Discard (``s.discard(x)``)
Comment thread
StanFromIreland marked this conversation as resolved.
Outdated
- *O*\ (1)
* - Union (``s | t``) [6]_
- *O*\ (len(*s*) + len(*t*))
* - Intersection (``s & t``, ``s.intersection(t)``) [6]_ [7]_
- *O*\ (min(len(*s*), len(*t*)))
* - Difference (``s - t``, ``s.difference(t)``) [6]_ [8]_
- *O*\ (len(*s*))
* - Difference update (``s.difference_update(t)``) [1]_ [6]_ [7]_
- *O*\ (min(len(*s*), len(*t*)))
* - Symmetric difference (``s ^ t``) [6]_
- *O*\ (len(*s*) + len(*t*))
* - Symmetric difference update (``s.symmetric_difference_update(t)``) [1]_ [6]_
- *O*\ (len(*t*))
* - Union (``s1 | s2``) [6]_
Comment thread
StanFromIreland marked this conversation as resolved.
Outdated
Comment thread
StanFromIreland marked this conversation as resolved.
Outdated
- *O*\ (len(*s1*) + len(*s2*))
* - Intersection (``s1 & s2``, ``s1.intersection(s2)``) [6]_ [7]_
Comment thread
StanFromIreland marked this conversation as resolved.
Outdated
- *O*\ (min(len(*s1*), len(*s2*)))
* - Difference (``s1 - s2``, ``s1.difference(s2)``) [6]_ [8]_
- *O*\ (len(*s1*))
* - Difference update (``s1.difference_update(s2)``) [1]_ [6]_ [7]_
- *O*\ (min(len(*s1*), len(*s2*)))
* - Symmetric difference (``s1 ^ s2``) [6]_
Comment thread
StanFromIreland marked this conversation as resolved.
Outdated
- *O*\ (len(*s1*) + len(*s2*))
* - Symmetric difference update (``s1.symmetric_difference_update(s2)``) [1]_ [6]_
- *O*\ (len(*s2*))
* - Get length (``len(s)``) [4]_
- *O*\ (1)

Comment thread
StanFromIreland marked this conversation as resolved.
Expand Down
Loading