Linked Questions
11 questions linked to/from How to describe algorithms, prove and analyse them?
98
votes
11
answers
29k
views
Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
- 72.7k
197
votes
3
answers
26k
views
Is there a system behind the magic of algorithm analysis?
There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
- 72.7k
5
votes
5
answers
2k
views
Optimal Algorithm for checking if a number is a multiple of three
I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation.
I currently have an assignment to work ...
- 247
13
votes
3
answers
463
views
Why larger input sizes imply harder instances?
Below, assume we're working with an infinite-tape Turing machine.
When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I ...
user20
24
votes
2
answers
341
views
Is Smoothed Analysis used outside academia?
Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?
user20
20
votes
1
answer
1k
views
Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
- 72.7k
3
votes
1
answer
2k
views
Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?
For Hoare's partitioning algorithm quicksort is implemented as such
...
user20767
1
vote
2
answers
1k
views
What is the significance of a Θ-bound on the running time of Mergesort?
While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it.
Given:
Mergesort takes $\Theta(n \log n)$ compares to sort ...
- 199
0
votes
0
answers
776
views
NFA: Parallel Bitmap Search vs Recursive Backtracking f
Why does an NFA that accepts/rejects bit strings implemented with a Recursive Backtracking algorithm outperform one that is written using a Parallel Bitmap search?
set up two tests for these ...
- 177
1
vote
1
answer
230
views
Big O - Equivalence: "Standard" definition vs Limit definition
This question is related to: Landau Notation, Definitions: Limits vs. Cormen's.
Consider functions $f, \ g : N \rightarrow R^{\geq0}$.
For small-$o$, the definition:
$$f(n)\in o(g(n)) \iff \forall ...
- 13
1
vote
1
answer
80
views
runtime of problems vs algorithms
I know that a solving a specific problem can have different runtimes on different models of computation. But can a specific algorithm have different runtimes on different models of computation?
Also, ...
- 143