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!
CodePudding user response:
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 ofn
dividesn
: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".