René's URL Explorer Experiment


Title: R23-T022: Empirical Complexity Analysis & Doctests for Exponential Search by mohammedsohail0301-dot · Pull Request #86 · S-AI-Projects/TheAlgorithms-Python · GitHub

Open Graph Title: R23-T022: Empirical Complexity Analysis & Doctests for Exponential Search by mohammedsohail0301-dot · Pull Request #86 · S-AI-Projects/TheAlgorithms-Python

X Title: R23-T022: Empirical Complexity Analysis & Doctests for Exponential Search by mohammedsohail0301-dot · Pull Request #86 · S-AI-Projects/TheAlgorithms-Python

Description: Describe your change Add an algorithm? Fix a bug or typo in an existing algorithm? Add or change doctests? -- Note: Please avoid changing both code and tests in a single pull request. Documentation change? Checklist I have read CONTRIBUTING.md. This pull request is all my own work -- I have not plagiarized. I know that pull requests will not be merged if they fail the automated tests. This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms. All new Python files are placed inside an existing directory. All filenames are in all lowercase characters with no spaces or dashes. All functions and variable names follow Python naming conventions. All function parameters and return values are annotated with Python type hints. All functions have doctests that pass the automated testing. All new algorithms include at least one URL that points to Wikipedia or another similar explanation. If this pull request resolves one or more open issues, then the description above includes the issue number(s) with a closing keyword: "Fixes #ISSUE-NUMBER". Description This pull request completes Task R23-T022: validating the empirical performance of Exponential Search against its theoretical time complexity $O(\log i)$ (where $i$ is the target's index) and comparing its element comparison counts against standard Binary Search. The docstring of exponential_search is updated with a concise mathematical derivation of $O(\log i)$ complexity and backed by measured element comparison counts across 7 doubling input sizes. Three new doctests covering edge cases (target at start, target at end, absent target) are added, and all 13 original doctests remain intact and passing. Type of Change Bug Fix New Feature UI/UX Improvement Performance Improvement Tests Documentation Refactoring / Maintenance CI/CD Changes Made searches/exponential_search.py: Updated docstring for exponential_search: documented theoretical time complexity $O(\log i)$ where $i$ is the target index with a 2-phase derivation (range bounding + bounded binary search). Included an empirical comparison counts table comparing Exponential Search vs. Binary Search across input sizes $n \in [1,000, \dots, 64,000]$. Added new doctests: Target at start: exponential_search([10, 20, 30, 40, 50, 60, 70, 80], 10) -> 0 Target at end: exponential_search([10, 20, 30, 40, 50, 60, 70, 80], 80) -> 7 Absent target: exponential_search([10, 20, 30, 40, 50, 60, 70, 80], 45) -> -1 All 13 existing doctests across binary_search_by_recursion and exponential_search preserved. work/R23-T022/: bench.py: Timing benchmark script with timeit across 7 doubling input sizes and instrumented comparison counters for targets at index $0$, $n // 2$, $n - 1$, and absent. exponential_search_benchmark.png: Dual-panel plot visualizing comparison counts vs. theoretical $2 \cdot \log_2 n$ curve and runtime scaling. FINDINGS.md: Complete theoretical derivation, mathematical bounds, and empirical analysis. test_output.txt: Doctest and pytest execution logs. ty_check.txt: Static type checker diagnostics. Measured Comparison Counts (Exponential vs. Binary Search) Size $n$ Target Position Index $i$ Exponential Search Binary Search Ratio (Exp / Bin) 1,000 start 0 1 17 0.06 1,000 mid 500 22 17 1.29 1,000 end 999 28 19 1.47 2,000 start 0 1 19 0.05 2,000 mid 1,000 23 19 1.21 2,000 end 1,999 31 21 1.48 4,000 start 0 1 21 0.05 4,000 mid 2,000 24 21 1.14 4,000 end 3,999 34 23 1.48 8,000 start 0 1 23 0.04 8,000 mid 4,000 25 23 1.09 8,000 end 7,999 37 25 1.48 16,000 start 0 1 25 0.04 16,000 mid 8,000 26 25 1.04 16,000 end 15,999 40 27 1.48 32,000 start 0 1 27 0.04 32,000 mid 16,000 27 27 1.00 32,000 end 31,999 43 29 1.48 64,000 start 0 1 29 0.03 64,000 mid 32,000 28 29 0.97 64,000 end 63,999 46 31 1.48 Testing python3 -m doctest -v searches/exponential_search.py -> 16/16 tests passed. uv run --with pytest pytest --doctest-modules searches/exponential_search.py -> 2 passed in 0.02s. uvx ruff check searches/exponential_search.py work/R23-T022/bench.py -> All checks passed. uvx ruff format --check searches/exponential_search.py work/R23-T022/bench.py -> 1 file already formatted. uvx ty check --exit-zero searches/exponential_search.py -> 0 diagnostics for the file. Additional Notes Findings: Exponential Search achieves $O(1)$ best case with exactly 1 comparison for targets at index $0$, reducing comparisons by up to 97% compared to Binary Search (1 vs 29 comparisons at $n=64,000$). For targets near the middle ($i=n/2$), Exponential Search is comparable to Binary Search ($\approx 28$ vs 29 comparisons). For targets near the end ($i=n-1$), Exponential Search performs $\approx 1.48\times$ comparisons of Binary Search due to the doubling phase, maintaining $O(\log n)$ asymptotic bound. A second clean branch student/E26B07F0850/R23-T022-upstream (and R23-T022-upstream) containing only the code change (no work/ folder) has been created and pushed for a later upstream PR.

Open Graph Description: Describe your change Add an algorithm? Fix a bug or typo in an existing algorithm? Add or change doctests? -- Note: Please avoid changing both code and tests in a single pull request. Document...

X Description: Describe your change Add an algorithm? Fix a bug or typo in an existing algorithm? Add or change doctests? -- Note: Please avoid changing both code and tests in a single pull request. Document...

Opengraph URL: https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86

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:aa9c96f0-f7f3-5279-025c-359bd352cacb
current-catalog-service-hashae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b
request-idD970:D0FAE:35199:4730B:6AFDFA3F
html-safe-nonce23336ebd2d51ff9a75509c658cf43c5f7319a7e55d3c47d9d5430879d1305250
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJEOTcwOkQwRkFFOjM1MTk5OjQ3MzBCOjZBRkRGQTNGIiwidmlzaXRvcl9pZCI6IjY5MzgzODkwMjg0NjI3ODcxMzUiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ==
visitor-hmac59431f17b6c65bd7c832af2880081e5c44c0045d48ca3f8f9d4beaff1382fcd3
hovercard-subject-tagpull_request:5360405232
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/S-AI-Projects/TheAlgorithms-Python/pull/86/files
twitter:imagehttps://avatars.githubusercontent.com/u/238795845?s=400&v=4
twitter:cardsummary_large_image
og:imagehttps://avatars.githubusercontent.com/u/238795845?s=400&v=4
og:image:altDescribe your change Add an algorithm? Fix a bug or typo in an existing algorithm? Add or change doctests? -- Note: Please avoid changing both code and tests in a single pull request. Document...
og:site_nameGitHub
og:typeobject
hostnamegithub.com
expected-hostnamegithub.com
Noneee3343385a977757dd145b28fabf4a119780f2615a5a36c5a89f66c9b3b5616d
turbo-cache-controlno-preview
diff-viewunified
go-importgithub.com/S-AI-Projects/TheAlgorithms-Python git https://github.com/S-AI-Projects/TheAlgorithms-Python.git
octolytics-dimension-user_id351892385
octolytics-dimension-user_loginS-AI-Projects
octolytics-dimension-repository_id1444141022
octolytics-dimension-repository_nwoS-AI-Projects/TheAlgorithms-Python
octolytics-dimension-repository_publictrue
octolytics-dimension-repository_is_forktrue
octolytics-dimension-repository_parent_id63476337
octolytics-dimension-repository_parent_nwoTheAlgorithms/Python
octolytics-dimension-repository_network_root_id63476337
octolytics-dimension-repository_network_root_nwoTheAlgorithms/Python
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
release43ae91995f6e2d5ff7a491f3de438f1f723adeaa
ui-targetfull
theme-color#1e2327
color-schemelight dark

Links:

Skip to contenthttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2FS-AI-Projects%2FTheAlgorithms-Python%2Fpull%2F86%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%2FS-AI-Projects%2FTheAlgorithms-Python%2Fpull%2F86%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=S-AI-Projects%2FTheAlgorithms-Python
Reloadhttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
Reloadhttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
Reloadhttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
S-AI-Projectshttps://github.com/S-AI-Projects
TheAlgorithms-Pythonhttps://github.com/S-AI-Projects/TheAlgorithms-Python
Codehttps://github.com/S-AI-Projects/TheAlgorithms-Python
Issues60 (60)https://github.com/S-AI-Projects/TheAlgorithms-Python/issues
Pull requests39 (39)https://github.com/S-AI-Projects/TheAlgorithms-Python/pulls
Actionshttps://github.com/S-AI-Projects/TheAlgorithms-Python/actions
Projectshttps://github.com/S-AI-Projects/TheAlgorithms-Python/projects
Security and qualityhttps://github.com/S-AI-Projects/TheAlgorithms-Python/security
Insightshttps://github.com/S-AI-Projects/TheAlgorithms-Python/insights
Sign up for GitHub https://github.com/signup?return_to=%2FS-AI-Projects%2FTheAlgorithms-Python%2Fissues%2Fnew%2Fchoose
terms of servicehttps://docs.github.com/terms
privacy statementhttps://docs.github.com/privacy
Sign inhttps://github.com/login?return_to=%2FS-AI-Projects%2FTheAlgorithms-Python%2Fissues%2Fnew%2Fchoose
mohammedsohail0301-dothttps://github.com/mohammedsohail0301-dot
S-AI-Projects:masterhttps://github.com/S-AI-Projects/TheAlgorithms-Python/tree/master
mohammedsohail0301-dot:student/E26B07F0850/R23-T022https://github.com/mohammedsohail0301-dot/TheAlgorithms-Python/tree/student/E26B07F0850/R23-T022
Conversation 0 https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86
Commits 2 https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/commits
Checks 0 https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/checks
Files changed https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
Please reload this pagehttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
R23-T022: Empirical Complexity Analysis & Doctests for Exponential Search https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#top
Show all changes 2 commits https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
e335a59 R23-T022: Empirical complexity analysis and doctests for exponential … mohammedsohail0301-dot Nov 17, 2026 https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/commits/e335a5933c86ce31cac24ecdc19d978192885d6e
784eac4 docs: update PR_BODY.md to match repository PR template mohammedsohail0301-dot Nov 17, 2026 https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/commits/784eac4e74fcc5bc371ee6f0c80b2b08cc8729d9
Clear filters https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
Please reload this pagehttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
Please reload this pagehttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files
exponential_search.py https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-0ad34f83dd56e8199ac08c8e84bec46297988fc479fd9a737d3c1cf012a59177
FINDINGS.md https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-00bc25b989706906e84669a9f655ae38d679dacc323703a63673d2b910c2e0e6
PR_BODY.md https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-3d3eb6e37c5467c87729f549c464975102e05b0e5602b42570cd7616461f1887
bench.py https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-2f601e46dd10029526e0adebf03421086180420893dd153761bae2a879f466a2
exponential_search_benchmark.png https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-2219fc1b775db5f5da0b2b63bbc88d6e725a3f1602e16c41894135e199d5fe69
test_output.txt https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-3aed637ee15e88eb6cc502427c55a43ed1ddc36afbfc6784a2a343e7a59680e1
ty_check.txt https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-3d6e2e4cfa9d563df4eb65d970097c0a01c93f0d9e2ff3c37253d70cd2d52b72
searches/exponential_search.pyhttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-0ad34f83dd56e8199ac08c8e84bec46297988fc479fd9a737d3c1cf012a59177
View file https://github.com/S-AI-Projects/TheAlgorithms-Python/blob/784eac4e74fcc5bc371ee6f0c80b2b08cc8729d9/searches/exponential_search.py
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/{{ revealButtonHref }}
https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-0ad34f83dd56e8199ac08c8e84bec46297988fc479fd9a737d3c1cf012a59177
https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-0ad34f83dd56e8199ac08c8e84bec46297988fc479fd9a737d3c1cf012a59177
https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-0ad34f83dd56e8199ac08c8e84bec46297988fc479fd9a737d3c1cf012a59177
https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-0ad34f83dd56e8199ac08c8e84bec46297988fc479fd9a737d3c1cf012a59177
work/R23-T022/FINDINGS.mdhttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-00bc25b989706906e84669a9f655ae38d679dacc323703a63673d2b910c2e0e6
View file https://github.com/S-AI-Projects/TheAlgorithms-Python/blob/784eac4e74fcc5bc371ee6f0c80b2b08cc8729d9/work/R23-T022/FINDINGS.md
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/{{ revealButtonHref }}
work/R23-T022/PR_BODY.mdhttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#diff-3d3eb6e37c5467c87729f549c464975102e05b0e5602b42570cd7616461f1887
View file https://github.com/S-AI-Projects/TheAlgorithms-Python/blob/784eac4e74fcc5bc371ee6f0c80b2b08cc8729d9/work/R23-T022/PR_BODY.md
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/{{ revealButtonHref }}
Please reload this pagehttps://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/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.