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
Switch back to l
  • Loading branch information
@StanFromIreland
StanFromIreland committed Aug 23, 2026
commit 116f21ec9f82125eeaa19453544e43bdd4716eb9
36 changes: 18 additions & 18 deletions Doc/library/time-complexity.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -33,42 +33,42 @@ If you need to add or remove at both ends, consider using a

* - Operation
- Complexity
* - Copy (``L.copy()``)
* - Copy (``l.copy()``)

@picnixz picnixz Aug 23, 2026

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This may seem silly, but I would suggest using L instead of l. Even with monospace fonts, it may not necessarily be readable for everyone.

@StanFromIreland StanFromIreland Aug 23, 2026

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Even with monospace fonts, it may not necessarily be readable for everyone.

I can see people confusing it with I, but I don't think that's a big issue here. It would however be inconsistent with the other tables, which would bug me.

@picnixz picnixz Aug 23, 2026

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Considering we are using l[i:j], I still think it's better to have L. It's not an issue to use another capitalization with other tables here. What matters is readability for me. Or you can use v for "vector".

@serhiy-storchaka serhiy-storchaka Aug 23, 2026

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Merge the list and tuple sections and use s, as in the main documentation.

@StanFromIreland StanFromIreland Aug 23, 2026

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For context, it was s originally in this PR and later changed at Ned's request. I've updated to L, I don't think merging is correct. Unlike the main docs, this is more of a reference.

- *O*\ (*n*)
* - Append (``L.append(x)``) [1]_
* - Append (``l.append(x)``) [1]_
- *O*\ (1)
* - Pop (``L.pop(k)``) [1]_ [2]_
* - Pop (``l.pop(k)``) [1]_ [2]_
- *O*\ (*n* - *k*)
* - Insert (``L.insert(k, x)``) [1]_ [2]_
* - Insert (``l.insert(k, x)``) [1]_ [2]_
- *O*\ (*n* - *k*)
Comment thread
StanFromIreland marked this conversation as resolved.
* - Get item (``L[k]``)
* - Get item (``l[k]``)
- *O*\ (1)
* - Set item (``L[k] = x``)
* - Set item (``l[k] = x``)
- *O*\ (1)
* - Delete item (``del L[k]``) [2]_
* - Delete item (``del l[k]``) [2]_
- *O*\ (*n* - *k*)
* - Iteration
- *O*\ (*n*)
* - Get slice (``L[i:j]``)
* - Get slice (``l[i:j]``)
- *O*\ (*j* - *i*)
* - Set slice (``L[i:j] = t``) [1]_
* - Set slice (``l[i:j] = t``) [1]_
- *O*\ (*j* - *i*) if len(*t*) == *j* - *i*,
otherwise *O*\ (*n* - *i* + len(*t*))
* - Delete slice (``del L[i:j]``)
* - Delete slice (``del l[i:j]``)
- *O*\ (*n* - *i*)
* - Extend (``L.extend(t)``) [1]_ [3]_
* - Extend (``l.extend(t)``) [1]_ [3]_
- *O*\ (len(*t*))
Comment thread
StanFromIreland marked this conversation as resolved.
* - Sort (``L.sort()``) [4]_
* - Sort (``l.sort()``) [4]_
- *O*\ (*n* log *n*)
* - Concatenate (``L1 + L2``)
- *O*\ (len(*L1*) + len(*L2*))
* - Multiply (``L * k``)
* - Concatenate (``l1 + l2``)
- *O*\ (len(*l1*) + len(*l2*))
* - Multiply (``l * k``)
- *O*\ (*nk*)
* - ``x in L``
* - ``x in l``
- *O*\ (*n*)
* - ``min(L)``, ``max(L)``
* - ``min(l)``, ``max(l)``
- *O*\ (*n*)
* - Get length (``len(L)``) [5]_
* - Get length (``len(l)``) [5]_
- *O*\ (1)

Comment thread
StanFromIreland marked this conversation as resolved.

Expand Down
Loading