Consider the following code to find the K th minimum element of an array:
FindKthMin(A[], k)
{
A = Sort(A);
return A[k];
}
Could it be an algorithm without specifying the sort details?
Can we say algorithm has no meaning without specifying the instruction set (target machine and its basic instruction set)
For example in BubbleSort should we specify the Swap(..) or Add(..) details? I mean what are those atomic instructions which would stop us to go further?
Or what is a formal definition for an algorithm step? Is there any general mathematical definition for it (like functions or something)?
It doesn’t make sense to talk about the step complexity of an algorithm without defining what a “step” is first. Algorithmic complexity is always relative to a model of computation, whether that be transitions of a Turing Machine, reductions in λ-calculus, instructions of a Random Access Machine or the number of comparisons when talking about comparison-based sorts such as bubble sort, quick sort, merge sort, tim sort etc.
Note also that algorithms don’t necessarily need to have “steps” at all. Analog algorithms are continuous, they don’t have steps.
1
When defining or talking about algorithmic complexity, you always have an (implicit) target abstract machine in mind (e.g. the RAM machine, the SECD machine, etc). Then the elementary steps are those of that target machine.
Bubble sort is O(n2) only with the assumption that compares are constant time. If you imagine sorting bignums it probably is no more the case (an individual compare is then probably proportional to the size of the compared numbers, i.e. to their logarithm)
10