Algorithms For Dummies

Distinguishing between different  

possible solutions

Recursion is part of many different algorithmic programming solutions, as you 

see  in  the  upcoming  chapters.  In  fact,  it’s  hard  to  get  away  from  recursion  in 

many cases because an iterative approach proves nonintuitive, cumbersome, and 

time consuming. However, you can create a number of different versions of the 

same solution, each of which has its own characteristics, flaws, and virtues.

---

CHAPTER 5

  Performing Essential Data Manipulations Using Python 

     111

The  solution  that  this  chapter  doesn’t  consider  is  sequential  search,  because  a 

sequential search generally takes longer than any other solution you can employ. 

In a best-case scenario, a sequential search requires just one comparison to com-

plete the search, but in a worst-case scenario, you find the item you want as the 

last check. As an average, sequential search requires 

(n+1)/2

 checks or O(n) time 

to complete.

The binary search in the previous section does a much better job than a sequential 

search does. It works on logarithmic time or O(log n). In a best-case scenario, it 

takes only one check, as with a sequential search, but the output from the example 

shows that even a worst-case scenario, where the value doesn’t even appear in the 

list, takes only six checks rather than the 21 checks that a sequential search would 

require.

This book covers a wide variety of search and sort algorithms because searching 

and sorting represent two major categories of computer processing. Think about 

how much time you spend Googling data each day. In theory, you might spend 

entire days doing nothing but searching for data. Search routines work best with 

sorted data, so you see the need for efficient search and sort routines. Fortunately, 

you don’t have to spend hours trying to figure out which search and sort routines 

work best. Sites such as Big-O Cheat Sheet, 

http://bigocheatsheet.com/

, pro-

vide you with the data needed to determine which solution performs best.

If you look at performance times alone, however, the data you receive can mislead 

you  into  thinking  that  a  particular  solution  will  work  incredibly  well  for  your 

application  when  in  fact  it  won’t.  You  must  also  consider  the  kind  of  data  you 

work with, the complexity of creating the solution, and a host of other factors. 

That’s why later examples in this book also consider the pros and cons of each 

approach — the hidden dangers of choosing a solution that seems to have poten-

tial and then fails to produce the desired result.

---

---