The Self-Taught Computer Scientist

Linear Complexity O(n)
Figure 1.3: Linear complexity

---

Chapter 1 What Is an Algorithm?
11
Log- Linear Time
An algorithm that runs in log- linear time grows as a combination (multiplication) of logarithmic and 
linear time complexities. For example, a log- linear algorithm might evaluate an O(log 
n) operation 
n times. In big O notation, you express a log- linear algorithm as O(n log n). Log- linear algorithms 
often divide a data set into smaller parts and process each piece independently. For example, many 
of the more efficient sorting algorithms you will learn about later, such as merge sort, are log- linear.
Figure 1.4 shows what a log- linear algorithm looks like when you plot it on a graph.
As you can see, log- linear complexity is not as efficient as linear time. However, its complexity does 
not grow nearly as quickly as quadratic, which you will learn about next.
Quadratic Time
After log- linear, the next most efficient time complexity is quadratic time. An algorithm runs in 
quadratic time when its performance is directly proportional to the problem’s size squared. In big O 
notation, you express a quadratic algorithm as O(
n**2).
Here is an example of an algorithm with quadratic complexity:
numbers = [1, 2, 3, 4, 5]
for i in numbers:
for j in numbers:
x = i * j
print(x)
Number of Customers
0
0
5
10
15
20
25
30
5
10
15
20
25
30
Number of Steps
Log-Linear Complexity O(n log n)
Figure 1.4: Log- linear complexity

---

Introduction to Algorithms
12
This algorithm multiplies every number in a list of numbers by every other number, stores the 
result in a variable, and prints it.
In this case, 
n is the size of your 
numbers
list. The equation for this algorithm’s time complexity is 
as follows:
f(n) = 1 + n * n * (1 + 1)
The (1 + 1) in the equation comes from the multiplication and print statement. You repeat the 
multiplication and print statement 
n * n times with your two nested 
for
loops. You can simplify the 
equation to this:
f(n) = 1 + (1 + 1) * n**2
which is the same as the following:
f(n) = 1 + 2 * n**2
As you may have guessed, the 
n**2 part of the equation overshadows the rest, so in big O notation, 
the equation is as follows:
O(n) = n**2
When you graph an algorithm with quadratic complexity, the number of steps increases sharply as 
the problem’s size increases (Figure 1.5).
Number of Customers
0
0
5
10
15
20
25
30
5
10
15
20
25
30
Number of Steps