I do not work in theory, but my work requires reading (and understanding) theory papers every once in a while. Once I understand a (set of) results, I discuss these results with people I work with, most of whom do not work in theory as well. During one of such discussions, the following question came up:
When does one say that two given algorithms are "similar"?
What do I mean by "similar"? Let us say that two algorithms are said to be similar if you can make either of the following claims in a paper without confusing/annoying any reviewer (better definitions welcomed):
Claim 1. "Algorithm $A$, which is similar to algorithm $B$, also solves problem $X$"
Claim 2. "Our algorithm is similar to Algorithm $C$"
Let me make it slightly more specific. Suppose we are working with graph algorithms. First some necessary conditions for the two algorithms to be similar:
- They must be solving the same problem.
- They must have the same high level intuitive idea.
For instance, talking about graph traversal, breadth-first and depth-first traversal satisfy the above two conditions; for shortest-path computations, breadth-first and Dijkstra's algorithm satisfy the above two conditions (on unweighted graphs, of course); etc.
Are these also sufficient conditions? More specifically, suppose two algorithms satisfy the necessary conditions to be similar. Would you indeed call them similar, if
- they have different asymptotic performance?
- for a special class of graphs, one algorithm requires $\Omega(n)$ time while the other requires $O(n^{1/3})$ time?
- they have different terminating conditions? (recall, they are solving the same problem)
- the pre-processing step is different in the two algorithms?
- the memory complexity is different in the two algorithms?
Edit: The question is clearly very context dependent and is subjective. I was hoping that the above five conditions, however, will allow getting some suggestions. I am happy to further modify the question and give more details, if needed to get an answer. Thanks!