The Self-Taught Computer Scientist

Chapter 1 What Is an Algorithm?
9
Logarithmic Time
Logarithmic time is the second most efficient time complexity. An algorithm takes logarithmic time 
when its run time grows in proportion to the logarithm of the input size. You see this time complexity 
in algorithms such as a binary search that can discard many values at each iteration. If this is not 
clear, don’t worry, because we will discuss this in depth later in the book. You express a logarithmic 
algorithm in big O notation as O(log 
n).
Figure 1.2 shows what it looks like when you plot a logarithmic algorithm.
The required number of steps grows more slowly in a logarithmic algorithm as the data set gets larger.
Number of Steps
0
0
5
10
15
20
25
30
5
10
15
20
25
30
Number of Customers
Constant Complexity O(1)
Figure 1.1: Constant complexity
Number of Customers
0
0
5
10
15
20
25
30
5
10
15
20
25
30
Number of Steps
Logarithmic Complexity O(log n)
Figure 1.2: Logarithmic complexity

---

Introduction to Algorithms
10
Linear Time
The next most efficient type of algorithm is one that runs in linear time. An algorithm that runs in 
linear time grows at the same rate as the size of the problem. You express a linear algorithm in big O 
notation as O(
n).
Suppose you must modify your free book program so that instead of giving a free book to the first 
customer of the day, you iterate through your list of customers and give them a free book if their name 
starts with the letter 
B. This time, however, your list of customers isn’t sorted alphabetically. Now you 
are forced to iterate through your list one by one to find the names that start with 
B.
free_book = False
customers = ["Lexi", "Britney", "Danny", "Bobbi", "Chris"]
for customer in customers:
if customer[0] == 'B':
print(customer)
When your customer list contains five items, your program takes five steps to complete. For a list 
of 10 customers, your program requires 10 steps; for 20 customers, 29 steps; and so on.
This is the equation for the time complexity of this program:
f(n) = 1 + 1 + n
And in big O notation, you can ignore the constants and focus on the part that dominates 
the equation:
O(n) = n
In a linear algorithm, as 
n gets bigger, the number of steps your algorithm takes increases by how-
ever much 
n increases (Figure 1.3).
Number of Customers
0
0
5
10
15
20
25
30
5
10
15
20
25
30
Number of Steps