An algorithm is a sequence of steps that solves a problem.

There are many competing definitions, but Donald Knuth’s is among the best known. He describes an algorithm as a definite, effective, and finite process that receives input and produces output based on this input.

Definiteness means that the steps are clear, concise, and unambiguous. Effectiveness means that you can perform each operation precisely to solve the problem. Finiteness means that the algorithm stops after a finite number of steps

There is often more than one algorithm we can use to solve a problem. For example, there are several different ways to sort a list. When several algorithms solve a problem, how do you know which one is best? Is it the simplest? The fastest? The smallest? Or something else? One way to judge an algorithm is by its run time. An algorithm’s run time is the amount of time it takes your computer to execute an algorithm written in a programming language like Python.

The second time you run your program, you should see a different run time. If you rerun your program, you will see yet another run time. The algorithm’s run time keeps changing because the available processing power your computer has when it runs your program varies and in turn affects the program’s run time. Further, this algorithm’s run time would be different on another computer. If you run it on a computer with less processing power, it would be slower, whereas it would be faster on a more powerful computer. Furthermore, this program’s run time is affected by the programming language you wrote it in.

Because an algorithm’s run time is affected by so many different variables, such as your computer’s processing power and the programming language, run time is not an effective way to compare two algorithms. Instead, computer scientists compare algorithms by looking at the number of steps they require. You can input the number of steps involved in an algorithm into a formula that can compare two or more algorithms without considering the programming language or computer.

As n gets bigger, the second part of your algorithm grows so much more quickly that the first part becomes irrelevant.

Because the important part of an algorithm is the part that grows the fastest as n gets bigger, computer scientists use big O notation to express an algorithm’s efficiency instead of a T(n) equation. Big O notation is a mathematical notation that describes how an algorithm’s time or space requirements (you will learn about space requirements later) increase as the size of n increases. Computer scientists use big O notation to create an order-of-magnitude function from T(n). An order of magnitude is a class in a classification system where each class is many times greater or smaller than the one before. In an order-of-magnitude function, you use the part of T(n) that dominates the equation and ignore everything else.

The part of T(n) that dominates the equation is an algorithm’s order of magnitude. These are the most commonly used classifications for order of magnitude in big O notation, sorted from the best (most efficient) to worst (least efficient):

Constant time

Logarithmic time

Linear time

Log-linear time

Quadratic time

Cubic time

Exponential time

Each order of magnitude describes an algorithm’s time complexity. Time complexity is the maximum number of steps an algorithm takes to complete as n gets larger. Let’s take a look at each order of magnitude.

Constant Time: The most efficient order of magnitude is called constant time complexity. An algorithm runs in constant time when it requires the same number of steps regardless of the problem’s size. The big O notation for constant complexity is O(1).

The number of steps your algorithm takes to complete does not get larger as the problem’s size increases. Therefore, it is the most efficient algorithm you can write because your algorithm’s run time does not change as your data sets grow larger.

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).The required number of steps grows more slowly in a logarithmic algorithm as the data set gets larger

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). In a linear algorithm, as n gets bigger, the number of steps your algorithm takes increases by however much n increases.

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. 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).

When you graph an algorithm with quadratic complexity, the number of steps increases sharply as the problem’s size increases.

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.

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.

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 polynomial 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 complexity involving trying to guess a numerical password consisting of n decimal digits by testing every possible combination is O(10**n).

Exponential scaling is the reason why it is so important to create long passwords.

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.

An algorithm’s best-case complexity is how it performs with ideal input, and an algorithm’s worst-case complexity is how it performs in the worst possible scenario for it. An algorithm’s average-case complexity is how it performs on average.

If you have to search through a list one by one a hundred times, on average you will find what you are looking for in O(n/2) time, which is the same as O(n) time in big-O notation. When comparing algorithms, you often start by looking at the average-case complexity. If you want to do a deeper analysis, you can also compare their best-case and worst-case complexities.

Computers have finite resources such as memory, so in addition to thinking about an algorithm’s time complexity, you should consider its resource usage. Space complexity is the amount of memory space your algorithm needs and includes fixed space, data structure space, and temporary space.

Fixed space is the amount of memory your program requires, and data structure space is the amount of memory your program needs to store the data set, for example, the size of a list you are searching. The amount of memory your algorithm uses to hold this data depends on the amount of input the problem requires. Temporary space is the amount of memory your algorithm needs for intermediary processing, for example, if your algorithm needs to temporarily copy a list to transfer data. You can apply the time complexity concepts you learned earlier to space complexity.

The decisions you make about algorithms can have enormous consequences in the real world. For example, say you are a web developer responsible for writing an algorithm that responds to a customer’s web request. Whether you decide to write a constant or quadratic algorithm could make the difference between your website loading in less than one second, making your customer happy, and taking more than a minute, which may cause you to lose customers before the request loads.

TermDefinitionAlgorithmA sequence of steps that solves a problem.Run timeThe amount of time it takes a computer to execute an algorithm written in a programming language.Size of the problemThe variable n in an equation that describes the number of steps in an algorithm.Big O notationA mathematical notation that describes how an algorithm’s time or space requirements increase as the size of n increases.Order of magnitudeA class in a classification system where each class is many times greater or smaller than the one before.Time complexityThe maximum number of steps an algorithm takes to complete as n gets larger.Constant timeAn algorithm runs in constant time when it requires the same number of steps regardless of the problem’s size.Logarithmic timeAn algorithm runs in logarithmic time when its run time grows in proportion to the logarithm of the input size.Linear timeAn algorithm runs in linear time when it grows at the same rate as the problem’s size.Log-linear timeAn algorithm runs in log-linear time when it grows as a combination (multiplication) of logarithmic and linear time complexities.Quadratic timeAn algorithm runs in quadratic time when its performance is directly proportional to the square of the size of the problem.Cubic timeAn algorithm runs in cubic time when its performance is directly proportional to the cube of the size of the problem.Polynomial timeAn algorithm runs in polynomial time when it scales as O(n**a), where a = 2 for quadratic time and a = 3 for cubic time.Exponential timeAn algorithm runs in exponential time when it contains a constant raised to the problem’s size.Brute-force algorithmA type of algorithm that tests every possible option.Best-case complexityHow an algorithm performs with ideal input.Worst-case complexityHow an algorithm performs in the worst possible scenario for it.Average-case complexityHow an algorithm performs on average.Space complexityThe amount of memory space an algorithm needs.Fixed spaceThe amount of memory a program requires.Data structure spaceThe amount of memory a program requires to store the data set.Temporary spaceThe amount of memory an algorithm needs for intermediary processing, for example, if your algorithm needs to temporarily copy a list to transfer data.