Linked Questions

90
votes
11answers
17k 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 ...
162
votes
3answers
17k 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 ...
5
votes
5answers
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 ...
12
votes
3answers
333 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 ...
23
votes
2answers
292 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?
20
votes
1answer
672 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 ...
3
votes
1answer
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 ...
1
vote
2answers
263 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 ...
0
votes
0answers
470 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 ...
1
vote
1answer
113 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 ...
1
vote
1answer
70 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, ...