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-profiling | 0 |
| react-import-map | react,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-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:aa9c96f0-f7f3-5279-025c-359bd352cacb |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | D970:D0FAE:35199:4730B:6AFDFA3F |
| html-safe-nonce | 23336ebd2d51ff9a75509c658cf43c5f7319a7e55d3c47d9d5430879d1305250 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJEOTcwOkQwRkFFOjM1MTk5OjQ3MzBCOjZBRkRGQTNGIiwidmlzaXRvcl9pZCI6IjY5MzgzODkwMjg0NjI3ODcxMzUiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | 59431f17b6c65bd7c832af2880081e5c44c0045d48ca3f8f9d4beaff1382fcd3 |
| hovercard-subject-tag | pull_request:5360405232 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | ///pull_requests/show/files |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files |
| twitter:image | https://avatars.githubusercontent.com/u/238795845?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/238795845?s=400&v=4 |
| og:image:alt | 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... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | ee3343385a977757dd145b28fabf4a119780f2615a5a36c5a89f66c9b3b5616d |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/S-AI-Projects/TheAlgorithms-Python git https://github.com/S-AI-Projects/TheAlgorithms-Python.git |
| octolytics-dimension-user_id | 351892385 |
| octolytics-dimension-user_login | S-AI-Projects |
| octolytics-dimension-repository_id | 1444141022 |
| octolytics-dimension-repository_nwo | S-AI-Projects/TheAlgorithms-Python |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | true |
| octolytics-dimension-repository_parent_id | 63476337 |
| octolytics-dimension-repository_parent_nwo | TheAlgorithms/Python |
| octolytics-dimension-repository_network_root_id | 63476337 |
| octolytics-dimension-repository_network_root_nwo | TheAlgorithms/Python |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 43ae91995f6e2d5ff7a491f3de438f1f723adeaa |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
| Skip to content | https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files#start-of-content |
| https://github.com/ |
| Sign in | https://github.com/login?return_to=https%3A%2F%2Fgithub.com%2FS-AI-Projects%2FTheAlgorithms-Python%2Fpull%2F86%2Ffiles |
| GitHubRepository hosting, code review, and collaboration | https://github.com/platform |
| CopilotAI coding agent for tasks, projects, and automated work | https://github.com/features/copilot |
| ActionsCI/CD and automation | https://github.com/features/actions |
| Code QualityQuality analysis, fixes, and enforcement | https://github.com/features/code-quality |
| CodespacesCloud development environments | https://github.com/features/codespaces |
| Code SecurityVulnerability detection and remediation | https://github.com/security/advanced-security/code-security |
| Secret ProtectionSecret scanning and leak prevention | https://github.com/security/advanced-security/secret-protection |
| All Features | https://github.com/features |
| Documentation | https://docs.github.com/en |
| Training | https://learn.github.com/skills |
| Certifications | https://learn.github.com/credentials |
| Build with Copilot | https://github.com/features/ai |
| Customize Copilot | https://docs.github.com/en/copilot/how-tos/copilot-on-github/customize-copilot/customize-copilot-overview |
| Integrations | https://github.com/marketplace |
| Trending repos | https://github.com/trending |
| GitHub Sponsors | https://github.com/open-source/sponsors |
| Developer articles | https://github.com/resources/articles |
| ChangelogYour source for the latest features, improvements, and fixes across GitHub products, all in one place. | https://github.blog/changelog/ |
| Enterprises | https://github.com/enterprise |
| Team | https://github.com/team |
| Startups | https://github.com/enterprise/startups |
| Nonprofits | https://github.com/solutions/industry/nonprofits |
| Healthcare | https://github.com/solutions/industry/healthcare |
| Financial services | https://github.com/solutions/industry/financial-services |
| Manufacturing | https://github.com/solutions/industry/manufacturing |
| Government | https://github.com/solutions/industry/government |
| See all industries | https://github.com/solutions/industry |
| Why GitHub | https://github.com/why-github |
| Customer Stories | https://github.com/customer-stories |
| Business insights | https://github.com/solutions/executive-insights |
| Trust Center | https://github.com/trust-center |
| GitHub Advanced SecurityEnterprise-grade code security | https://github.com/security/advanced-security |
| Copilot for businessEnterprise-grade AI features | https://github.com/features/copilot/copilot-business |
| Premium SupportEnterprise-grade 24/7 support | https://github.com/enterprise/premium-support |
| Documentation | https://docs.github.com/en |
| Resource center | https://github.com/resources |
| Blog | https://github.blog/ |
| Events & webinars | https://github.com/resources/events |
| Community Forum | https://github.com/orgs/community/discussions |
| Customer Stories | https://github.com/customer-stories |
| Integrations | https://github.com/marketplace |
| Customer support | https://help.github.com/ |
| Training | https://learn.github.com/skills |
| GitHub Status | https://www.githubstatus.com/ |
| About | https://github.com/about |
| Partners | https://github.com/partners |
| Changelog | https://github.blog/changelog/ |
| GitHub UniverseThe event for developers, by developers — talks, workshops, and what’s next for GitHub. | https://githubuniverse.com/ |
| Pricing | https://github.com/pricing |
| Sign in | https://github.com/login?return_to=https%3A%2F%2Fgithub.com%2FS-AI-Projects%2FTheAlgorithms-Python%2Fpull%2F86%2Ffiles |
| Sign up | https://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 |
| Reload | https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files |
| Reload | https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files |
| Reload | https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files |
| S-AI-Projects | https://github.com/S-AI-Projects |
| TheAlgorithms-Python | https://github.com/S-AI-Projects/TheAlgorithms-Python |
| Code | https://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 |
| Actions | https://github.com/S-AI-Projects/TheAlgorithms-Python/actions |
| Projects | https://github.com/S-AI-Projects/TheAlgorithms-Python/projects |
| Security and quality | https://github.com/S-AI-Projects/TheAlgorithms-Python/security |
| Insights | https://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 service | https://docs.github.com/terms |
| privacy statement | https://docs.github.com/privacy |
| Sign in | https://github.com/login?return_to=%2FS-AI-Projects%2FTheAlgorithms-Python%2Fissues%2Fnew%2Fchoose |
| mohammedsohail0301-dot | https://github.com/mohammedsohail0301-dot |
| S-AI-Projects:master | https://github.com/S-AI-Projects/TheAlgorithms-Python/tree/master |
| mohammedsohail0301-dot:student/E26B07F0850/R23-T022 | https://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 page | https://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 page | https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files |
| Please reload this page | https://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.py | https://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.md | https://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.md | https://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 page | https://github.com/S-AI-Projects/TheAlgorithms-Python/pull/86/files |
|
| https://github.com |
| Terms | https://docs.github.com/site-policy/github-terms/github-terms-of-service |
| Privacy | https://docs.github.com/site-policy/privacy-policies/github-privacy-statement |
| Security | https://github.com/security |
| Status | https://www.githubstatus.com/ |
| Community | https://github.community/ |
| Docs | https://docs.github.com/ |
| Contact | https://support.github.com?tags=dotcom-footer |
Viewport: width=device-width
URLs of crawlers that visited me.