What is a Great Algorithm?

Question

I’m taking classes from Introducing the Analysis of Complexity. I was told that an example of an optimal algorithm is the algorithm for finding the smallest value between elements of an array of integers:

int min = vet[0];
for (int i = 1; i < n; i++){
    if (min > vet[i]){
        min = vet[i];
    }
}

1. What’s a great algorithm?
2. Why is this algorithm great?
3. And how to determine if other algorithms are great?

Answer 1

An optimal algorithm is one that can solve a particular problem using as few resources as possible. However, we enter here a crop that ends up generating not a single great option, but a curve of several possibilities of great.

For example, the bitonic merge Sort is more efficient or less efficient than a merge Sort traditional? If you compute the time it takes for the algorithm to finish running, then the bitonic merge Sort is better: it performs in less time. However, it only achieves this improvement doing more computations: then it consumes more energy.

He can do more computations in less time because of parallelism.

It also has other aspects: merge Sort is an algorithm of stable ordering, but the bitonic merge Sort is not.

So, as with many other optimization problems, we need to understand what we want to optimize and what constraints we provide. For example, if there were a quadratic amount of processing cores running, it would be possible to know in O(log n) which the smallest number.

---

Now, your teacher said this algorithm is great, but is it great at all times to know the minimum in a data collection? The answer is: no, there are affairs where the constraints of the problem say there may be another more efficient algorithm.

For example, if the vector is previously ordered, the optimal algorithm would be O(1) with vet[0]. Although it is a strange case for this problem (taking the minimum), this circumstance (ordered vector) is common to happen in other problems. For example, whether an element appears in an array. If there is no ordering guarantee, it is necessary to check all the list elements, 1 to 1, to ensure that the data sought really is not there. Now, if by chance the problem already provides a ordered vector, search for an element now needs a logarithmic amount, an algorithm called binary search.

Another point of knowing if an algorithm is great is relative to its computation constraint. For example, this algorithm is great in time for mono-processed things. Eventually we can have more than 2 processing cores available, so we could split the processing load in half, using (roughly) the same amount of processing but half the time.

---

Now, about direct answers to questions:

What’s a great algorithm?

It is that algorithm which, for the problem in question, consumes the minimum of a given resource.

Why is this algorithm great?

Because there is no way to do fewer computations in a mono-processed environment, and there is also no way to use fewer variables.

Other possibilities of making another algorithm for this problem (identifying the smallest element in a nontrivially empty vector) would cause more computations performed, or use more memory.

An example would be to treat especially the first time one enters the loop:

int min = 0;
for (int i = 0; i < n; i++) {
  if (i == 0) {
    min = v[i];
  } else {
    if (v[i] < min) {
      min = v[i];
    }
  }
}

Note that here I am putting an extra condition on each repetition, which is to check if I am in the first element. This becomes unnecessary because the algorithm provided already treats trivially the first element.

Another alternative (even worse in terms of performance, in my view) would be to work with Integer (Integer min = null), being the first case identified as being min == null:

Integer min = null;
for (int i = 0; i < n; i++) {
  if (min == null) {
    min = v[i];
  } else {
    if (v[i] < min) {
      min = v[i];
    }
  }
}

A possible advantage of this using the Integer it would only be possible to see in a situation: if it is possible to inform a size 0 for the vector size (indicated by n). In this case, the null means that there is no minimum. But it would be much more efficient to do so:

Integer min;

if (n == 0) {
  min = null;
} else {
  int otherMin = v[0];
  for (int i = 1; i < n; i++) {
    if (v[i] < otherMin) {
      otherMin = v[i];
    }
  }
  min = otherMin;
}

Another point that is less great than that proposed by your teacher by one execution:

int min = vet[0];
for (int i = 0; i < n; i++){
    if (min > vet[i]){
        min = vet[i];
    }
}

This alternative checks the position 0 that trivially is already in the variable min at the beginning of the execution, so this is done for nothing.

I can think of two more alternatives:

int min = v[0];

for (int i = 1; i < n; i++) {
  min = v[i] < min? v[0]: min;
}

In that alternative there is always n assignments and n comparisons, then losing in the amount of assignments made (which in the best case of the original algorithm is only the first).

The last alternative would be to start with int min = Integer.MAX_VALUE; and scroll through the entire list.

And how to determine if other algorithms are great?

Will depend much of each problem and which computer models are used. Normally you think of monoprocessors, so maybe this can be taken as a restriction a priori. In other cases, we must take into account that computing can be done in a distributed way. We also need to know what we want optimize.

There are problems that we can solve using additional memory, but in less time. There are also situations where you should answer various instances of the same problem, then we can do an initial processing and reuse the "learned" answer several times when the problem is asked. For example, we can use the eratosthenes sieve to determine whether the number is prime or not, but to run the whole sieve to answer whether 15 is prime is spending too much processing.

There are cases where you need to save as much memory as possible, even if it means spending more processing time.

We can try to simplify by talking about "great" as being that algorithm in a mono-processed environment run in less time. Unfortunately, to prove that, we need some way deplete all possible algorithmic possibilities. There are cases where it is possible to do this, usually for problems in class P. Even with these limitations, I cannot imagine a general method to do this. At most, I can only think of how compare two algorithms.