The Self-Taught Computer Scientist

Introduction to Algorithms
4
someone can’t use the input to guess the output. Also, many algorithms in data science are not strict 
about correctness. For example, it may be sufficient for an algorithm to estimate output, as long as the 
estimate’s uncertainty is known. In most cases, however, your algorithms should fulfill all the previous 
requirements. If you write an algorithm for making scrambled eggs, the user might not be happy if, 
occasionally, the algorithm produces an omelet or boiled eggs instead.
Analyzing Algorithms
There is often more than one algorithm we can use to solve a problem. For example, there are several 
different ways to sort a list. When several algorithms solve a problem, how do you know which one 
is best? Is it the simplest? The fastest? The smallest? Or something else?
One way to judge an algorithm is by its run time. An algorithm’s run time is the amount of time it 
takes your computer to execute an algorithm written in a programming language like Python. For 
example, here is an algorithm in Python that counts from 1 to 5 and prints each number:
for i in range(1, 6):
print(i)
You can measure this algorithm’s run time using Python’s built- in 
time
module to track how long 
your computer takes to execute it:
import time
start = time.time()
for i in range(1, 6):
print(i)
end = time.time()
print(end – start)
>> 1
>> 2
>> 3
>> 4
>> 5
>> 0.15141820907592773
When you run your program, it prints the numbers from 1 to 5 and outputs the time it took to 
execute. In this case, it took 0.15 seconds.
Now, rerun your program:
import time
start = time.time()
for i in range(1, 6):

---

Chapter 1 What Is an Algorithm?
5
print(i)
end = time.time()
print(end – start)
>> 1
>> 2
>> 3
>> 4
>> 5
>> 0.14856505393981934
The second time you run your program, you should see a different run time. If you rerun your 
program, you will see yet another run time. The algorithm’s run time keeps changing because the 
available processing power your computer has when it runs your program varies and in turn affects 
the program’s run time.
Further, this algorithm’s run time would be different on another computer. If you run it on a com-
puter with less processing power, it would be slower, whereas it would be faster on a more powerful 
computer. Furthermore, this program’s run time is affected by the programming language you wrote 
it in. For example, the run time would be faster if you run this same program in C because C can be 
faster than Python.
Because an algorithm’s run time is affected by so many different variables, such as your computer’s 
processing power and the programming language, run time is not an effective way to compare two 
algorithms. Instead, computer scientists compare algorithms by looking at the number of steps they 
require. You can input the number of steps involved in an algorithm into a formula that can compare 
two or more algorithms without considering the programming language or computer. Let’s take a look 
at an example. Here is your program from earlier that counts from 1 to 5:
for i in range(1, 6):
print(i)
Your program takes five steps to complete (it goes through a loop five times and prints 
i
each time). 
You can express the number of steps your algorithm requires with this equation:
f(n) = 5 
If you make your program more complicated, your equation will change. For example, you may 
want to keep track of the sum of all the numbers you are printing:
count = 0
for i in range(1, 6):
print(i)
count += i

---