Algorithms For Dummies

Evaluating Algorithms

Gaining insights into precisely how algorithms work is important because other-

wise you can’t determine whether an algorithm actually performs in the way you 

need it to. In addition, without good measurements, you can’t perform accurate 

comparisons  to  know  whether  you  really  do  need  to  discover  a  new  method  of 

solving  a  problem  when  an  older  solution  works  too  slowly  or  uses  too  many 

---

36

 

   

  PART 1 

 Getting Started

resources. The reality is that you’ll use algorithms made by others most of the 

time, potentially devising a few of your own. Knowing the basis to use to compare 

different solutions and deciding between them is an essential skill when dealing 

with algorithms.

The issue of efficiency has been part of discovering and designing new algorithms 

since the concept of algorithms first came into being, which is why you see so 

many  different  algorithms  competing  to  solve  the  same  problem  (sometimes  a 

real embarrassment of riches). The concept of measuring the size of the functions 

within an algorithm and analyzing how the algorithm works isn’t new; both Ada 

Lovelace and Charles Babbage considered the problems of algorithm efficiency in 

reference to computers as early as 1843 (see a short history of the Babbage engine 

at 

http://www.computerhistory.org/babbage/adalovelace/

).

Donald Knuth (

http://www-cs-faculty.stanford.edu/~uno/

), computer scien-

tist, mathematician, professor emeritus at Stanford University, and author of the 

milestone, multivolume book The Art of Computer Programming (Addison-Wesley), 

devoted much of his research and studies to comparing algorithms. He strived to 

formalize  how  to  estimate  the  resource  needs  of  algorithms  in  a  mathematical 

way and to allow a correct comparison between alternative solutions. He coined 

the term analysis of algorithms, which is the branch of computer science devoted to 

understanding  how  algorithms  work  in  a  formal  way.  The  analysis  measures 

resources required in terms of the number of operations an algorithm requires to 

reach a solution or by its occupied space (such as the storage an algorithm requires 

in computer memory).

Analysis  of  algorithms  requires  some  mathematical  understanding  and  some 

computations, but it’s extremely beneficial in your journey to discover, appreci-

ate, and effectively use algorithms. This topic is considerably more abstract than 

other topics in this book. To make the discussion less theoretical, later chapters 

present  more  practicalities  of  such  measurement  by  examining  algorithms 

together in detail. The following sections provide you with the basics.