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.