What is an Algorithm?

An algorithm is a precise and unambiguous specification of a sequence of computational steps that can be mechanically performed¹. From this, we can think of a function that receives a value or a set of values as input and returns a value or a set of values as its output.

An algorithm can be correct or incorrect. It is correct when, given its input parameters, its output is correct and, therefore, solves the computational problem for which it was developed. An incorrect algorithm, on the other hand, may stop with an incorrect output or may not stop at all for some input instances. Still, some incorrect algorithms can still have useful applications.

There can be different algorithms that solve the same problem, some more efficient, that is, faster than others. But, not every problem has an efficient solution. Such problems are known as NP-complete.

NP-complete problems are very interesting: even though no efficient algorithm has been found for this class of problems, it has not been proven that it is not possible to find an efficient algorithm (from class P, which can be solved in polynomial time) for such a problem. Moreover, if there were an efficient algorithm to solve an NP-complete problem, it would mean that there is an efficient algorithm for all NP-complete problems.

Algorithmic Complexity

When we talk about algorithms, most of the time we are interested in the growth rate of time and space required to solve increasingly larger instances of certain problems. If we are interested in the time a particular algorithm takes to perform its function, we are interested in its time complexity. And the behavior of the time complexity limit of our algorithm in relation to the increase of the problem instances is called asymptotic time complexity. And it is this asymptotic complexity that determines the size of the problem that can be solved by algorithms².

If an algorithm takes a time $cn^2$ for a constant $c$ to process an input of size $n$, we say that the complexity of the algorithm is of the order of $n^2$, or, in Bachmann–Landau notation (also called asymptotic notation and Big O notation), the algorithm has complexity $O(n^2)$.

To get a better idea of what this means in relation to the runtime of our algorithm, consider that one unit of time on the computer on which we run our algorithm is 1 millisecond. Now, we want to know what the maximum size of input that our algorithm can process within a certain time limit (one second, one hour, and one day). Note, in the table below, how much the complexity of the algorithm interferes with the maximum size of the input it can handle, given the time limit:

Time Complexity	1 second	1 minute	1 hour
$n$	1000	60000	360000
$n \log_2 n$	140	4895	204095
$n^2$	31	244	1897
$n^3$	10	39	153
$2^n$	9	15	21

Even though we can build faster computers, the increase in the execution speed of less efficient algorithms would not be so significant, so we should always seek the most efficient algorithm to address a given problem.

Footnotes

1. AHO, Alfred V.; ULLMAN, Jeffrey D. Foundations of Computer Science. Stanford, 1994. ↩

2. AHO, Alfred V.; HOPCROFT, John E.; ULLMAN, Jeffrey D. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ↩