 Working with Algorithmic Functions - dummies

A function in mathematics is simply a way to map some inputs to a response. Expressed in a different way, a function is a transformation (based on math operations) that transforms (maps) your input to an answer.

For certain values of input (usually denoted by the letters x or n), you have a corresponding answer using the math that defines the function. For instance, a function like f(n) = 2n tells you that when your input is a number n, your answer is the number n multiplied by 2.

Using the size of the input does make sense given that this is a time-critical age and people’s lives are crammed with a growing quantity of data. Making everything a mathematical function is a little less intuitive, but a function describing how an algorithm relates its solution to the quantity of data it receives is something you can analyze without specific hardware or software support. It’s also easy to compare with other solutions, given the size of your problem. Analysis of algorithms is really a mind-blowing concept because it reduces a complex series of steps into a mathematical formula.

Moreover, most of the time, an analysis of algorithms isn’t even interested in defining the function exactly. What you really want to do is compare a target function with another function. These comparison functions appear within a set of proposed functions that perform poorly when contrasted to the target algorithm. In this way, you don’t have to plug numbers into functions of greater or lesser complexity; instead, you deal with simple, premade, and well-known functions. It may sound rough, but it’s more effective and is similar to classifying the performance of algorithms into categories, rather than obtaining an exact performance measurement.

The set of generalized functions is called Big O notation, and you often encounter this small set of functions (put into parentheses and preceded by a capital O) used to represent the performance of algorithms. The figure shows the analysis of an algorithm. A Cartesian coordinate system can represent its function as measured by RAM simulation, where the abscissa (the x coordinate) is the size of the input and the ordinate (the y coordinate) is its resulting number of operations.

You can see three curves represented. Input size matters. However, quality also matters (for instance, when ordering problems, it’s faster to order an input which is already almost ordered). Consequently, the analysis shows a worst case, f1(n), an average case, f2(n), and a best case, f3(n).

Even though the average case might give you a general idea, what you really care about is the worst case, because problems may arise when your algorithm struggles to reach a solution. The Big O function is the one that, after a certain `n0` value (the threshold for considering an input big), always results in a larger number of operations given the same input than the worst-case function `f1`. Thus, the Big O function is even more pessimistic than the one representing your algorithm, so that no matter the quality of input, you can be sure that things cannot get worse than that.