3
$\begingroup$

Is there a technical term for a pair $(u,v)$ of algorithms, such that $u$ and $v$ have an identical output for each input (I include the option if not halting as a possible output), but they have different complexity (either time or space) as a function of their input?

An example of such a pair is (bubble sort, quicksort)

$\endgroup$
3
$\begingroup$

What you are talking about is very narrow, there is no term that describes it exactly.

However, a closely related concept that you might be interested in is extensional equivalence as opposed to intensional equivalence. Intuitively, two objects are extensionally equivalent if they have the same external properties, and intensionally equivalent if they have the exact same definition.

Generally, mathematics and logic define equality as (some form of) extensional equivalence; for instance, the Zermelo-Fraenkel set theory includes some form of the following axiom:

$$ \forall x \forall y [\forall z (z \in x \Leftrightarrow z \in y) \Rightarrow x = y] $$

Since functions are really relations, and relations are really sets, two functions that are point-by-point identical are literally the same function. But still, I believe that most of us would agree that even though quicksort and bubblesort are somewhat related, they are not the same thing.

So the real question here is what is the thing you call "the algorithm quicksort"? It's certainly more than just a program: quicksort written in C is not the same program as quicksort written in Haskell, but we would still call both quicksort. But at the same time it's not really just a function, defined by its input and output: in order to deserve the name "quicksort" you also have to operate in a certain way.

It's not a question I have a good answer for, there is no precise and universal definition of "algorithm" (yet).

In the meantime, I would say that quicksort and bubblesort are extensionally equivalent but not intensionally equivalent.


(or, at least, none I'm aware of)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.