Linked Questions

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 ...
Raphael's user avatar
  • 72.6k
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 ...
Raphael's user avatar
  • 72.6k
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 ...
Haikal Yeo's user avatar
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 ...
user avatar
24 votes
2 answers
340 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?
user avatar
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 ...
Raphael's user avatar
  • 72.6k
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 ...
user avatar
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 ...
vivek's user avatar
  • 199
0 votes
0 answers
775 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 ...
foobarbaz's user avatar
  • 177
1 vote
1 answer
228 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 ...
jdoes's user avatar
  • 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, ...
Armon Safai's user avatar