The Self-Taught Computer Scientist

Quadratic complexity O(n^2) 
Figure 1.5: Quadratic complexity

---

Chapter 1 What Is an Algorithm?
13
As a general rule, if your algorithm contains two nested loops running from 1 to 
n (or from 0 to
n − 1), its time complexity will be at least O(n**2). Many sorting algorithms such as insertion and 
bubble sort (which you will learn about later in the book) follow quadratic time.
Cubic Time
After quadratic comes cubic time complexity. An algorithm runs in cubic time when its performance 
is directly proportional to the problem’s size cubed. In big O notation, you express a cubic algorithm 
as O(
n**3). An algorithm with a cubic complexity is similar to quadratic, except n is raised to the 
third power instead of the second.
Here is an algorithm with cubic time complexity:
numbers = [1, 2, 3, 4, 5]
for i in numbers:
for j in numbers:
for h in numbers:
x = i + j + h
print(x)
The equation for this algorithm is as follows:
f(n) = 1 + n * n * n * (1 + 1)
Or as follows:
f(n) = 1 + 2 * n**3
Like an algorithm with quadratic complexity, the most critical part of this equation is 
n**3, which 
grows so quickly it makes the rest of the equation, even if it included 
n**2, irrelevant. So, in big O 
notation, quadratic complexity is as follows:
O(n) = n**3
While two nested loops are a sign of quadratic time complexity, having three nested loops running 
from 0 to 
n means that the algorithm will follow cubic time. You will most likely encounter cubic time 
complexity if your work involves data science or statistics.

---

Introduction to Algorithms