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 98
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.
0
votes
Algorithm with no closed-form exact complexity
There are plenty of simple algorithms whose running-time is unknown in any form. Therefore, their "complexity" can not be expressed in closed-form either, for suitable notions of "closed-form".
Note …
- 72.9k
3
votes
Accepted
Say that a stack frame only contains total functions: could the maximum stack size be static...
No. That would allow you to determine the runtime of any given (recursive) program (assuming it always terminates), but that is not a computable problem.
- 72.9k
3
votes
Accepted
Clarification notation in CLRS runtime analysis
The number of iterations of the while-loop depends on j which changes during across iterations of the for-loop. Thus, the total runtime of lines 5-7 must depend on $j$, and the runtime of lines 6-7 ma …
- 72.9k
1
vote
Calculating time complexity of a code which may be incorrect
Correctness is relative -- with respect to what specification¹?
Technically, C code is never run; it is always compiled to some machine code. So, if you want to be really nitpicky, it is impossible t …
- 72.9k
3
votes
Accepted
What is the time complexity of an algorithm that calls a polynomial time algorithm?
I assume $n$ is the number of entries in array/set A.
Yes, since polynomials are closed against multiplication; specifically, $n(n-1) \cdot p(n)$ is always polynomially bounded as long as $p(n)$ is …
- 72.9k
3
votes
Cost of break statement
Depends on how close you want to look.
On face value, break, continue, etc. are implemented by unconditional jumps, which are (under most RAM-/CPU-like models) primitive instructions of the machine. …
- 72.9k
3
votes
Accepted
How do I determine the basic operation of this algorithm?
"Basic operations" are whatever you choose. You may get different results based on your choice, which is great as it leads to understanding algorithms better! You may have seen the number of compariso …
- 72.9k
1
vote
Why does $O(n \log n)$ seem so linear?
Just some general observations.
O(n log n) is only an upper bound. If it's not tight, that's your explanation right there.
A Θ(n log n) running time can have many different components, for instance
…
- 72.9k
6
votes
Optimal Algorithm for checking if a number is a multiple of three
Answering your questions one by one:
From what you know, you don't; you'd have to show that no algorithm can be better, that is it attains a (tight) lower bound.
I don't know what you mean by "cheat …
- 72.9k
4
votes
My algorithm is different from CLRS' -- is it wrong?
The core issue here is not a factual one, but one of expectations and (meta) logic:
But the solution they give in the Lecture Notes is [different from mine]. So my question is: why is my solution wro …
- 72.9k
14
votes
Why use comparisons instead of runtime for comparing two algorithms?
This is actually a deep issue that has some methodic and some pragmatic answers. I assume you want to know something about the algorithm(s) at hand. If you want to know which algorithm works better on …
- 72.9k
5
votes
What constitutes one unit of time in runtime analysis?
The ultimate goal is "execution time in seconds" or more generally (disregarding modern CPU features) "number of clock cycles".
As it turns out, this is hard to analyse, and it is also machine or at l …
- 72.9k
4
votes
Accepted
How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?
There are some things to consider here.
Conceptually, an algorithm that iterates once over the input array has runtime $\Omega(n)$ (and $O(n)$ if it does constant-time work per element), $n$ being th …
- 72.9k
10
votes
What is the asymptotic runtime of this nested loop?
We have lots of questions about the time complexity of sums, and the answer is the same every time:
Loops translate to sums.¹
Every other shortcut will get you into trouble.
In your case, you seem …
- 72.9k
1
vote
Accepted
Converting a recursive algorithm to a runtime function
The key is to use right - left as $n$ for the parameter of the runtime recursion. What is the size of the subparts?
Closer hint:
Almost finished:
- 72.9k