The Self-Taught Computer Scientist

14
Both quadratic and cubic time complexities are special cases of a larger family of polynomial time 
complexities. An algorithm that runs in polynomial time scales as O(
n**a), where a = 2 for quadratic 
time and 
a = 3 for cubic time. When designing your algorithms, you generally want to avoid polyno-
mial scaling when possible because the algorithms can get very slow as 
n gets larger. Sometimes you 
can’t escape polynomial scaling, but you can find comfort knowing that the polynomial complexity 
is still not the worst case, by far.
Exponential Time
The honor of the worst time complexity goes to exponential time complexity. An algorithm that runs 
in exponential time contains a constant raised to the size of the problem. In other words, an algorithm 
with exponential time complexity takes 
c raised to the nth power steps to complete. The big O notation 
for exponential complexity is O(
c**n), where c is a constant. The value of the constant doesn’t matter. 
What matters is that 
n is in the exponent.
Fortunately, you won’t encounter exponential complexity often. One example of exponential com-
plexity involving trying to guess a numerical password consisting of 
n decimal digits by testing every 
possible combination is O(10**
n).
Here is an example of password guessing with O(10**
n) complexity:
pin = 931
n = len(pin)
for i in range(10**n):
if i == pin:
print(i)
The number of steps this algorithm takes to complete grows incredibly fast as 
n gets larger. When 
n is 1, this algorithm takes 10 steps. When n is 2, it takes 100 steps. When n is 3, it takes 1,000 steps. 
As you can see, at first, an exponential algorithm looks like it doesn’t grow very quickly. However, 
eventually, its growth explodes. Guessing a password with 8 decimal digits takes 100 million steps, 
and guessing a password with 10 decimal digits takes more than 10 billion steps. Exponential scaling 
is the reason why it is so important to create long passwords. If someone tries to guess your password 
using a program like this, they can easily guess it if your password is four digits. However, if your 
password is 20 digits, it is impossible to crack because the program will take longer to run than a 
person’s life span.
This solution to guessing a password is an example of a brute- force algorithm. A brute- force 
algorithm is a type of algorithm that tests every possible option. Brute- force algorithms are not usually 
efficient and should be your last resort.
Figure 1.6 compares the efficiency of the algorithms we have discussed.

---