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, ifthey 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!
When are two algorithms said to be similar?
ds.algorithms;graph algorithms