Program efficiency: Algorithm vs Implementation

Question

I was watching a lecture about program efficiency where the professor said:

"If I measure running time, it will certainly vary as the algorithm change. (...) But one of the problems is that it will also vary as a function of the implementation (...) If I use a loop that's got a couple of more steps inside of it in one algorithm than another, it's going to change the time."

I am having a hard time wrapping my head around the implementation's influence.

So my question is: Why can't we consider those extra loop steps inside of one algorithm, when compared to the other, simply something that is necessary for it to run and that is also a part of the algorithm's efficiency? Or did I completely miss the point here?

Thank you!

Answer 1

They are pointing out the difference between "algorithm" and "specific code written in a programming language". "Algorithm" is somewhat of a vague term and "algorithms" are often described in pseudo-code that can be either very detailed, or not detailed at all.

For instance, consider the following algorithm, to test whether a number n is prime or not:

• If any number d between 2 and the square root of n divides n:

• Return False (n is not prime)

• Else:

• Return True (n is prime)

How exactly do you loop over the numbers between 2 and the square root? You could do:

// IMPLEMENTATION A

bool is_prime(int n)
{
    int s = sqrt(n);
    for (int d = 2; d <= s; d++)
    {
        if (n % d == 0)
            return false;
    }
    return true;
}

or:

// IMPLEMENTATION B

bool is_prime(int n)
{
    for (int d = 2; d * d <= n; d++)
    {
        if (n % d == 0)
            return false;
    }
    return true;
}

Those two codes both implement the algorithm that I described. However, they might not have exactly the same runtime, since the former requires computing sqrt(n) once, but the latter requires computing d * d at every iteration in the loop.

Computer scientists want to be able to discuss the complexity of the algorithm that I described above in pseudo-code. And they don't want someone to give the boring answer "Sorry, the complexity of that algorithm is impossible to calculate, because we don't know if it's implementation A or implementation B".