0

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)?

Improve this question

2 Answers 2

Reset to default
4

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.

Improve this answer
1
  • It should be said that algorithms operating on qbits do not have the same algorithm. Changing the state of one qbit modifies them all, but it counts as a single operation since you're not cycling the entire array of qbits.
    – Neil
    Commented Feb 19, 2015 at 9:10
2

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)

Improve this answer
10
  • In fact, the running time of comparison-based sorts is often specifically expressed in terms of the number of comparisons, not a generic notion of "step". I believe the C++ spec, for example, specifies the maximum number of calls to the <= operator as a measure of complexity.
    – Jörg W Mittag
    Commented Feb 19, 2015 at 7:08
  • @JörgWMittag: when looking at sort operations, normally one does not just count the number of comparisons, but also the number of "swaps".
    – Doc Brown
    Commented Feb 19, 2015 at 7:11
  • @DocBrown: Ah, you're right. I vaguely remember some machine model from one of my algorithms courses, where one could only swap neighboring elements, I believe. (Or some similar restriction.) Which had some interesting repercussions for the running times (and even implementability, I believe) of some of the well-known sorting algorithms.
    – Jörg W Mittag
    Commented Feb 19, 2015 at 7:38
  • I don't mean necessarily the time complexity, but even the meaning of the step? it also depends on the target machine?
    – Ahmad
    Commented Feb 19, 2015 at 8:02
  • 1
    @Ahmad: a "step" is what you choose it to be. For the purpose you have in mind. For example, when analysing run time complexity, it makes sense to work with atomic steps with already known run time complexity, typically O(1) steps.
    – Doc Brown
    Commented Feb 19, 2015 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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