Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithm-analysis
Search options not deleted
user 71238
Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.
1
vote
Is my algorithm to find the median of 2 sorted arrays O(log(m + n))?
Judging from your description and your code, you are basically doing a merge of the two array but stop at the median. This means that your main loop (body) is executed $(m + n) / 2 \in O(m + n)$ times …
- 1,536
6
votes
Accepted
Why does the time hierarchy theorem use a rather intricate diagonal argument?
The output size does not scale with (time) complexity of problems in general.
In fact, complexity theorists are largely interested in decision problems for which the output will either be 0 or 1.
- 1,536
2
votes
Accepted
What recurrence describes the time complexity of this algorithm?
Partial answer: The problem admits an $O(n^{\log_3(2)}) \leq O(n^{0.631})$ algorithm.
The algorithm $\mathcal A$ works as follows:
Query $x = A[n/3]$ and $y = A[2n/3]$.
If $x = y$, return $\max \{x, …
- 1,536