When are two algorithms said to be "similar"? 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!
It is a tough problem to give even a coherent definition of "Algorithm A is similar to Algorithm B". For one, I don't think that "they must be solving the same problem" is a necessary condition. Often when one says in a paper that "the algorithm $A$ of Theorem $2$ is similar to the algorithm $B$ in Theorem $1$", the algorithm $A$ is actually solving a different problem than that of $B$, but has some minor modifications to handle the new problem. 

Even trying to determine what it means for two algorithms to be the same is an interesting and difficult problem. See the paper "When are two algorithms the same?" http://research.microsoft.com/~gurevich/Opera/192.pdf