I came across this problem:
Find the mistake of the following inductive proof:
Theorem: all algorithms have the same time complexity.
Proof: (By induction on the number of algorithms.)
The statement is trivial for one algorithm.
Let the statement holds for some K. Consider (K+1) algorithms. Remove any and algorithm, then the remaining algorithms have the same time complexity according to the assumption. Return the algorithm back and remove another one, then the remaining algorithms have the same time complexity again. It means all (K + 1) have the same time complexity.
Q.E.D.
My attempt: Consider the case of 2 algorithms (K+1) = 2, each with different time complexity. By removing any of them, we have only one algorithm where the statement holds. However, this is not two if each one has different time complexity.
Is this the correct way to solve the problem?
Thanks.
There are two mistakes here.
Mistake 1) To prove all members of some given set $A$ have some property, it is not valid to argue by induction on the number of elements of $A$: "By induction on the number of (all) algorithms ..." is not a valid method of proof.
Mistake 2) The induction scheme in the proposed proof is valid if what we were trying to prove is: if $X$ is any finite set of algorithms, then all algorithms in $X$ have the same time complexity. Or in other words, writing $t(A)$ for the time complexity of an algorithm $A$, that $t$ is constant on any finite set of algorithms $X$. However, the inductive step fails in this proof: you can't infer that $t$ is constant on the two-element set $\{A, B\}$ from the (obvious fact) that it is constant on the singleton sets $\{A\}$ and $\{B\}$. (The rhetoric in the question about moving algorithms in and out of the set sounds convincing but does not work when $K = 2$. I think this is what you had in mind in your attempt at the question.)