René's URL Explorer Experiment


Title: Add a page detailing the time complexity of operations on built-in types by StanFromIreland · Pull Request #154363 · python/cpython · GitHub

Open Graph Title: Add a page detailing the time complexity of operations on built-in types by StanFromIreland · Pull Request #154363 · python/cpython

X Title: Add a page detailing the time complexity of operations on built-in types by StanFromIreland · Pull Request #154363 · python/cpython

Description: Inspired by @nedbat's post on Discourse: One page in the wiki that I think should be in the docs is Time Complexity. It seems like important information about CPython and should be documented. The page's location isn't ideal, but we don't have a better place for it currently. We discussed this at the last Docs Community meeting, but didn't come up with a better place to put it, and creating new top level sections is in my opinion, out of scope (as we'd need to move other pages as well). If it's desired we can do it in a future PR. I spend a while considering how to best present time complexity here, avoiding complexity ;-) The wiki pages splits it into amortised, worst, best and averages cases (each type had a selection of those), but I think that it would be too confusing for readers. As such I give the average case, and put the details in the prose/footnotes. The numbers are, hopefully, correct, as I don't think I missed any quirks (at least I don't know of any ;-). But I'd appreciate a review from the experts here, maybe Serhiy or Tim could please take a peek?

Open Graph Description: Inspired by @nedbat's post on Discourse: One page in the wiki that I think should be in the docs is Time Complexity. It seems like important information about CPython and should be documented....

X Description: Inspired by @nedbat's post on Discourse: One page in the wiki that I think should be in the docs is Time Complexity. It seems like important information about CPython and should be documen...

Opengraph URL: https://github.com/python/cpython/pull/154363

X: @github

direct link

Domain: github.com

react-profiling0
react-import-mapreact,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322
route-pattern/:user_id/:repository/pull/:id/files(.:format)
route-controllerpull_requests
route-actionfiles
fetch-noncev2:fa6248cd-ea8b-0956-fb47-2462385c2034
current-catalog-service-hashae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b
request-idC63E:928E2:330F4A7:4416B0D:6B01F831
html-safe-nonce5f945d3d7f4164839e2167c4485d4a917dbf2062673348d8f3f4034dd0677b8b
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJDNjNFOjkyOEUyOjMzMEY0QTc6NDQxNkIwRDo2QjAxRjgzMSIsInZpc2l0b3JfaWQiOiIyNzE4MDQ2MjAwODIwNTI5MjAxIiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0=
visitor-hmac39884f232e0b6cdfb968eaf505f3bc18e527203e887d113d51a29e4e2c948283
hovercard-subject-tagpull_request:4100148444
github-keyboard-shortcutsrepository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///pull_requests/show/files
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/python/cpython/pull/154363/files
twitter:imagehttps://avatars.githubusercontent.com/u/89152624?s=400&v=4
twitter:cardsummary_large_image
og:imagehttps://avatars.githubusercontent.com/u/89152624?s=400&v=4
og:image:altInspired by @nedbat's post on Discourse: One page in the wiki that I think should be in the docs is Time Complexity. It seems like important information about CPython and should be documented....
og:site_nameGitHub
og:typeobject
hostnamegithub.com
expected-hostnamegithub.com
None87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456
turbo-cache-controlno-preview
diff-viewunified
go-importgithub.com/python/cpython git https://github.com/python/cpython.git
octolytics-dimension-user_id1525981
octolytics-dimension-user_loginpython
octolytics-dimension-repository_id81598961
octolytics-dimension-repository_nwopython/cpython
octolytics-dimension-repository_publictrue
octolytics-dimension-repository_is_forkfalse
octolytics-dimension-repository_network_root_id81598961
octolytics-dimension-repository_network_root_nwopython/cpython
turbo-body-classeslogged-out env-production page-responsive full-width
disable-turbotrue
browser-stats-urlhttps://api.github.com/_private/browser/stats
browser-errors-urlhttps://api.github.com/_private/browser/errors
release423dbb54c5e7bfecc838eb387c1435eb3d0e760d
ui-targetfull
theme-color#1e2327
color-schemelight dark

Links:

Skip to contenthttps://github.com/python/cpython/pull/154363/files#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fpull%2F154363%2Ffiles
GitHubRepository hosting, code review, and collaborationhttps://github.com/platform
CopilotAI coding agent for tasks, projects, and automated workhttps://github.com/features/copilot
ActionsCI/CD and automationhttps://github.com/features/actions
Code QualityQuality analysis, fixes, and enforcementhttps://github.com/features/code-quality
CodespacesCloud development environmentshttps://github.com/features/codespaces
Code SecurityVulnerability detection and remediationhttps://github.com/security/advanced-security/code-security
Secret ProtectionSecret scanning and leak preventionhttps://github.com/security/advanced-security/secret-protection
All Featureshttps://github.com/features
Documentationhttps://docs.github.com/en
Traininghttps://learn.github.com/skills
Certificationshttps://learn.github.com/credentials
Build with Copilothttps://github.com/features/ai
Customize Copilothttps://docs.github.com/en/copilot/how-tos/copilot-on-github/customize-copilot/customize-copilot-overview
Integrationshttps://github.com/marketplace
Trending reposhttps://github.com/trending
GitHub Sponsorshttps://github.com/open-source/sponsors
Developer articleshttps://github.com/resources/articles
ChangelogYour source for the latest features, improvements, and fixes across GitHub products, all in one place.https://github.blog/changelog/
Enterpriseshttps://github.com/enterprise
Teamhttps://github.com/team
Startupshttps://github.com/enterprise/startups
Nonprofitshttps://github.com/solutions/industry/nonprofits
Healthcarehttps://github.com/solutions/industry/healthcare
Financial serviceshttps://github.com/solutions/industry/financial-services
Manufacturinghttps://github.com/solutions/industry/manufacturing
Governmenthttps://github.com/solutions/industry/government
See all industrieshttps://github.com/solutions/industry
Why GitHubhttps://github.com/why-github
Customer Storieshttps://github.com/customer-stories
Business insightshttps://github.com/solutions/executive-insights
Trust Centerhttps://github.com/trust-center
GitHub Advanced SecurityEnterprise-grade code securityhttps://github.com/security/advanced-security
Copilot for businessEnterprise-grade AI featureshttps://github.com/features/copilot/copilot-business
Premium SupportEnterprise-grade 24/7 supporthttps://github.com/enterprise/premium-support
Documentationhttps://docs.github.com/en
Resource centerhttps://github.com/resources
Bloghttps://github.blog/
Events & webinarshttps://github.com/resources/events
Community Forumhttps://github.com/orgs/community/discussions
Customer Storieshttps://github.com/customer-stories
Integrationshttps://github.com/marketplace
Customer supporthttps://help.github.com/
Traininghttps://learn.github.com/skills
GitHub Statushttps://www.githubstatus.com/
Abouthttps://github.com/about
Partnershttps://github.com/partners
Changeloghttps://github.blog/changelog/
GitHub UniverseThe event for developers, by developers — talks, workshops, and what’s next for GitHub.https://githubuniverse.com/
Pricinghttps://github.com/pricing
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fpull%2F154363%2Ffiles
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fpull_requests%2Fshow%2Ffiles&source=header-repo&source_repo=python%2Fcpython
Reloadhttps://github.com/python/cpython/pull/154363/files
Reloadhttps://github.com/python/cpython/pull/154363/files
Reloadhttps://github.com/python/cpython/pull/154363/files
pythonhttps://github.com/python
cpythonhttps://github.com/python/cpython
Codehttps://github.com/python/cpython
Issues5k+ (5k+)https://github.com/python/cpython/issues
Pull requests2.4k (2.4k)https://github.com/python/cpython/pulls
Actionshttps://github.com/python/cpython/actions
Projectshttps://github.com/python/cpython/projects
Security and qualityhttps://github.com/python/cpython/security
Insightshttps://github.com/python/cpython/insights
Sign up for GitHub https://github.com/signup?return_to=%2Fpython%2Fcpython%2Fissues%2Fnew%2Fchoose
terms of servicehttps://docs.github.com/terms
privacy statementhttps://docs.github.com/privacy
Sign inhttps://github.com/login?return_to=%2Fpython%2Fcpython%2Fissues%2Fnew%2Fchoose
StanFromIrelandhttps://github.com/StanFromIreland
python:mainhttps://github.com/python/cpython/tree/main
StanFromIreland:timecomplexity-dochttps://github.com/StanFromIreland/cpython/tree/timecomplexity-doc
Conversation 132 https://github.com/python/cpython/pull/154363
Commits 18 https://github.com/python/cpython/pull/154363/commits
Checks 40 https://github.com/python/cpython/pull/154363/checks
Files changed https://github.com/python/cpython/pull/154363/files
Please reload this pagehttps://github.com/python/cpython/pull/154363/files
Add a page detailing the time complexity of operations on built-in types https://github.com/python/cpython/pull/154363/files#top
Show all changes 18 commits https://github.com/python/cpython/pull/154363/files
80088bf Add a 'Time complexity of operations on built-in types' section StanFromIreland Jul 8, 2026 https://github.com/python/cpython/pull/154363/commits/80088bf411a9d86b09fec88b49bc01a323e03b70
84b95f9 Ned's suggestion for blog post rec. StanFromIreland Jul 8, 2026 https://github.com/python/cpython/pull/154363/commits/84b95f997c54664fd57ba7ddff57734bcff9f7b6
1982202 Revert that StanFromIreland Jul 21, 2026 https://github.com/python/cpython/pull/154363/commits/19822027cce3e6b660863781265e9b5f4bfc03d0
64fb553 Little fixups StanFromIreland Jul 21, 2026 https://github.com/python/cpython/pull/154363/commits/64fb553c9e51160a826d8cdce678732029ca1918
0392d7e Apply review suggestions from Pieter and Bénédikt StanFromIreland Jul 21, 2026 https://github.com/python/cpython/pull/154363/commits/0392d7e57b74fcb1357c0fcf7315dbc549339fb2
9e1a82a Address Pieter's very helpful review StanFromIreland Aug 6, 2026 https://github.com/python/cpython/pull/154363/commits/9e1a82a832ac39e853953c5d2f9a67e5635c4915
f19c249 Merge branch 'main' into timecomplexity-doc StanFromIreland Aug 10, 2026 https://github.com/python/cpython/pull/154363/commits/f19c2499d48b09b2898351a1c89e5d169afc1474
d0ca44c Simplify complexity notation addressing part of Serhiy's comments StanFromIreland Aug 11, 2026 https://github.com/python/cpython/pull/154363/commits/d0ca44cf09cc5e5ede99bd1628dc0e0e7a12154d
7e297d6 Carol's suggestion StanFromIreland Aug 12, 2026 https://github.com/python/cpython/pull/154363/commits/7e297d6722fdb3964ba4cc600fa30ed418427528
22d5586 Ned's review StanFromIreland Aug 13, 2026 https://github.com/python/cpython/pull/154363/commits/22d5586b18cc4d34f307f6dff37bca1ce66367b2
5f21510 Missed a few, oops! StanFromIreland Aug 13, 2026 https://github.com/python/cpython/pull/154363/commits/5f215109a316472719399f50c50a2fb578347586
29e2017 Ned's review StanFromIreland Aug 13, 2026 https://github.com/python/cpython/pull/154363/commits/29e201719115875c4727963f24dddf3f702f0696
4d223f1 Address @dg-pb's review re. reverse string search complexity StanFromIreland Aug 13, 2026 https://github.com/python/cpython/pull/154363/commits/4d223f1dc5c4eede42cff0e0abeccb1bb196cdb2
a893080 Try to simplify footnote StanFromIreland Aug 13, 2026 https://github.com/python/cpython/pull/154363/commits/a893080f481cab48cb5423e9475f7180c83fb8bd
c4a75fd Remove note StanFromIreland Aug 20, 2026 https://github.com/python/cpython/pull/154363/commits/c4a75fd2965414bee17dd484eb5640297a16bd2b
eac04b8 Drop "very" StanFromIreland Aug 22, 2026 https://github.com/python/cpython/pull/154363/commits/eac04b845e5970857fdc1f9aba74ee7772037e93
27e9cd6 Address Bénédikt's review StanFromIreland Aug 23, 2026 https://github.com/python/cpython/pull/154363/commits/27e9cd6c1251bfaacf6c4a3c32fcadfcfba28904
116f21e Switch back to `l` StanFromIreland Aug 23, 2026 https://github.com/python/cpython/pull/154363/commits/116f21ec9f82125eeaa19453544e43bdd4716eb9
Clear filters https://github.com/python/cpython/pull/154363/files
Please reload this pagehttps://github.com/python/cpython/pull/154363/files
Please reload this pagehttps://github.com/python/cpython/pull/154363/files
design.rst https://github.com/python/cpython/pull/154363/files#diff-c24c9b6e50c13da8ffb334befe62bef7df5f24603e41d293cfe8bd8848f941b4
programming.rst https://github.com/python/cpython/pull/154363/files#diff-f14918b87c23a58e6f4050eae0e4c196c6dfa019b1c6540cab5123035f7aec7f
glossary.rst https://github.com/python/cpython/pull/154363/files#diff-dfb52ee6e68075f904da6e69ed1799c5cbf1185c279968a807787d69ae2e8cf5
index.rst https://github.com/python/cpython/pull/154363/files#diff-46910936d9f6bfb1908619469a251d4129b271d5abee1bb3a2d0a72ec2a127ec
stdtypes.rst https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
time-complexity.rst https://github.com/python/cpython/pull/154363/files#diff-7bfdcc9a4f3721a55cd9a2b47456246300a2618d1d8db19d7d3b71b267f3f180
datastructures.rst https://github.com/python/cpython/pull/154363/files#diff-e22b6613fb97dcbe5b2b8eb0bad1a71f55122473f4573353d8046d7c2d421865
Doc/faq/design.rsthttps://github.com/python/cpython/pull/154363/files#diff-c24c9b6e50c13da8ffb334befe62bef7df5f24603e41d293cfe8bd8848f941b4
View file https://github.com/StanFromIreland/cpython/blob/116f21ec9f82125eeaa19453544e43bdd4716eb9/Doc/faq/design.rst
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/154363/{{ revealButtonHref }}
https://github.com/python/cpython/pull/154363/files#diff-c24c9b6e50c13da8ffb334befe62bef7df5f24603e41d293cfe8bd8848f941b4
https://github.com/python/cpython/pull/154363/files#diff-c24c9b6e50c13da8ffb334befe62bef7df5f24603e41d293cfe8bd8848f941b4
https://github.com/python/cpython/pull/154363/files#diff-c24c9b6e50c13da8ffb334befe62bef7df5f24603e41d293cfe8bd8848f941b4
https://github.com/python/cpython/pull/154363/files#diff-c24c9b6e50c13da8ffb334befe62bef7df5f24603e41d293cfe8bd8848f941b4
Doc/faq/programming.rsthttps://github.com/python/cpython/pull/154363/files#diff-f14918b87c23a58e6f4050eae0e4c196c6dfa019b1c6540cab5123035f7aec7f
View file https://github.com/StanFromIreland/cpython/blob/116f21ec9f82125eeaa19453544e43bdd4716eb9/Doc/faq/programming.rst
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/154363/{{ revealButtonHref }}
https://github.com/python/cpython/pull/154363/files#diff-f14918b87c23a58e6f4050eae0e4c196c6dfa019b1c6540cab5123035f7aec7f
https://github.com/python/cpython/pull/154363/files#diff-f14918b87c23a58e6f4050eae0e4c196c6dfa019b1c6540cab5123035f7aec7f
Doc/glossary.rsthttps://github.com/python/cpython/pull/154363/files#diff-dfb52ee6e68075f904da6e69ed1799c5cbf1185c279968a807787d69ae2e8cf5
View file https://github.com/StanFromIreland/cpython/blob/116f21ec9f82125eeaa19453544e43bdd4716eb9/Doc/glossary.rst
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/154363/{{ revealButtonHref }}
https://github.com/python/cpython/pull/154363/files#diff-dfb52ee6e68075f904da6e69ed1799c5cbf1185c279968a807787d69ae2e8cf5
https://github.com/python/cpython/pull/154363/files#diff-dfb52ee6e68075f904da6e69ed1799c5cbf1185c279968a807787d69ae2e8cf5
Doc/library/index.rsthttps://github.com/python/cpython/pull/154363/files#diff-46910936d9f6bfb1908619469a251d4129b271d5abee1bb3a2d0a72ec2a127ec
View file https://github.com/StanFromIreland/cpython/blob/116f21ec9f82125eeaa19453544e43bdd4716eb9/Doc/library/index.rst
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/154363/{{ revealButtonHref }}
https://github.com/python/cpython/pull/154363/files#diff-46910936d9f6bfb1908619469a251d4129b271d5abee1bb3a2d0a72ec2a127ec
Please reload this pagehttps://github.com/python/cpython/pull/154363/files
https://github.com/python/cpython/pull/154363/files#diff-46910936d9f6bfb1908619469a251d4129b271d5abee1bb3a2d0a72ec2a127ec
Doc/library/stdtypes.rsthttps://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
View file https://github.com/StanFromIreland/cpython/blob/116f21ec9f82125eeaa19453544e43bdd4716eb9/Doc/library/stdtypes.rst
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/154363/{{ revealButtonHref }}
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
https://github.com/python/cpython/pull/154363/files#diff-08a31a70dd1f6d97aa8dacdce77db4de04c700d9949be1af611a595186aad5b3
Please reload this pagehttps://github.com/python/cpython/pull/154363/files
Please reload this pagehttps://github.com/python/cpython/pull/154363/files
https://github.com
Termshttps://docs.github.com/site-policy/github-terms/github-terms-of-service
Privacyhttps://docs.github.com/site-policy/privacy-policies/github-privacy-statement
Securityhttps://github.com/security
Statushttps://www.githubstatus.com/
Communityhttps://github.community/
Docshttps://docs.github.com/
Contacthttps://support.github.com?tags=dotcom-footer

Viewport: width=device-width


URLs of crawlers that visited me.