Algorithms For Dummies

Working with functions

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 

---

CHAPTER 2

  Considering Algorithm Design 

     39

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 multi-

plied 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 every-

thing 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 some-

thing  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 algo-

rithm. 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 func-

tions. 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 perfor-

mance measurement.

The  set  of  generalized  functions  is  called  Big O  notation,  and  in  this  book,  you 

often encounter this small set of functions (put into parentheses and preceded by 

a capital O) used to represent the performance of algorithms. Figure 2-1 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 opera-

tions. 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, 

f

1

(n)

, an average case, 

f

2

(n)

, and a best case, 

f

3

(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 

n

0

 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 

f

1

. 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.

---

40