What Is an Algorithm? Search, Sorting and Big-O Explained

In everyday life

Type a destination into a map app, and a route appears in seconds. Type words into a search engine, and useful pages rise to the top out of a huge number of pages. A video app suggests videos you are likely to watch.

Now picture putting a shuffled deck of playing cards in number order. You might keep finding the smallest card and pulling it out. Or you might split the cards into piles and then combine them. People always pick some method, and the time it takes depends a lot on the method.

Steps like these, which lead to an answer, are called an algorithm. In the news, you often see phrases like "the social media algorithm." This article explains what an algorithm is and checks, with numbers, why better steps make computing faster.

An algorithm is a clear set of steps that ends

An algorithm writes out, in order, the stages for solving a problem. It takes in the ingredients (the input), goes through fixed stages and produces an answer (the output). For example, here is how to find the largest number in a list. Treat the first number as the "largest so far." Compare it with the next number, and if the next one is bigger, it becomes the new largest so far. Repeat this until the last number.

Two conditions set an algorithm apart from just "a way of doing things." First, every stage has a clear meaning, so anyone who follows it does the same thing. Second, for any input, it always finishes at some point. The computer scientist Donald Knuth listed five properties of an algorithm in his famous textbook. They are these two, plus input, output and being possible to actually carry out.

The CPU, the central part of a computer, simply carries out simple instructions like "add" and "compare," one at a time. An algorithm is the idea of which instructions to line up, in which order, to get the answer. "What Is a CPU?" explains how a CPU works.

The word "algorithm" comes from the name of al-Khwarizmi, a mathematician of the 9th century. He wrote a book on calculating with Indian numerals, the digits we use today. It was translated into Latin and spread across Europe. The form of his name used in that translation became the source of the word.

Two ways to search: one by one, or by halves

Say you need to find the person with a certain ID number in a list of 1 million members. The most obvious way is to compare the entries one at a time, starting from the top. This method is called "linear search." If you are unlucky, you make 1 million comparisons, right up to the last entry.

If the list is sorted by number, there is a better way. First, compare with the entry in the middle. If the number you want is bigger, it cannot be in the first half, so you keep only the second half. Repeat this, and each comparison cuts the range in half. This method is called binary search.

Keep halving 1 million entries, and you get 500,000, then 250,000, and so on. By the 20th comparison, the search is always settled. That is because multiplying 2 by itself 20 times gives 1,048,576, which is more than 1 million. So binary search finishes in at most 20 comparisons, whether or not the number is in the list. 1 million comparisons versus 20 is a 50,000-fold difference.

When people look up a word in a paper dictionary, they do not turn the pages one by one from the start. They open it at a rough guess, see whether the word is before or after, and narrow it down. Binary search repeats this narrowing mechanically, always at the exact middle.

Binary search does have one condition: the data must already be sorted. In a shuffled list, comparing with the middle tells you nothing about which side the target is on. That is why sorting, which we look at next, is also an important job.

Sorting can also differ by tens of thousands of times

Putting data into a set order is called "sorting." Here we compare two methods. As a measure of the work, we count how many times two cards are compared to see which is bigger.

The first is the obvious method. Among the cards not yet placed, find the smallest one and add it to the end of the row. To find the smallest, you have to look at all the remaining cards. With n cards, the first round takes n−1 comparisons, the second takes n−2, and so on, one fewer each time. The total is about n×n÷2 comparisons. (This method is called selection sort.)

The second is "merge sort." Split the pile of cards in half, then split each half again, until every pile has one card. Next, combine the small piles two at a time. Compare the top cards of the two piles and take the smaller one. Repeat this, and you get one sorted pile.

Merge sort is fast because it takes only a few rounds of halving. Even 1 million cards become single cards after about 20 halvings. In each round, combining only looks at every card once. So the number of comparisons is roughly "number of cards × number of halvings." The number of times you halve n to reach 1 is written log₂n, so this is n×log₂n comparisons.

The merge sort column is an estimate from n×log₂n, and the actual number of comparisons is a little lower. For one deck, the difference is only about 4 times, so either method is fine when sorting by hand. But the gap grows wider and wider as the number of cards grows. If you want to watch them in action, the sorting algorithm visualizer lets you compare several methods.

Time complexity: compare how the work grows

What matters in these examples is not the amount of work but how it grows. When the data doubles, the work for linear search doubles. Binary search needs just one more step. The obvious sorting method needs four times as much.

How the work grows as the amount of data grows is called time complexity. It is a yardstick for comparing different steps that solve the same problem, regardless of how fast the computer is.

Time complexity is written with an "O," as in O(n) or O(n²). This way of writing is called Big-O notation, and the n inside the brackets is the amount of data. O(n²) means "the work grows roughly in proportion to n×n." Constant factors like "÷2" are dropped. They do not change how many times more work you need when the data doubles.

The log in this table is counted the same way as before: how many halvings it takes to reach 1. The O(n²) row says 1 trillion, not the 500 billion in the earlier table. That is because the factor "÷2" is dropped.

The most troublesome one is O(2ⁿ). Suppose you try every way of choosing which of 50 items to pick. That is 2 multiplied by itself 50 times, about 1.1 quadrillion (1,100 trillion) ways. Even checking 1 billion ways per second, it takes about 13 days. With 51 items, it doubles again. To try different numbers, the time complexity (Big-O) comparison tool calculates the counts and times.

A faster computer cannot rescue a roundabout method

Picture a computer that can make 1 billion comparisons per second. To keep things simple, assume every comparison takes the same time. Sorting 1 million items with the obvious method takes about 500 billion comparisons. That is about 500 seconds, a little over 8 minutes. Merge sort needs about 20 million comparisons, which takes 0.02 seconds.

So what if you buy a computer that is 100 times faster? Even the obvious method then takes 5 seconds. Yet merge sort on the old computer is still 250 times faster.

Next, say the data grows tenfold, to 10 million items. The work for the obvious method grows 100 times, so even the 100-times-faster computer takes about 500 seconds. Merge sort on the old computer takes about 0.23 seconds. With an O(n²) method, just ten times more data uses up all of a 100-fold speedup.

Thanks to progress in semiconductors, computers have kept getting faster for decades ("What Is Moore's Law?"). This is why research on algorithms is still essential.

Algorithms that made history

Dijkstra's algorithm (1959): finding the shortest route

Suppose you know a set of places and the length of each road between them. This method finds the shortest route from a starting point to every place. It locks in the "shortest distance so far" for places in order of how close they are to the start. Then it updates the distances of the places beyond them. Edsger Dijkstra of the Netherlands designed it in 1956 and published it in a paper in 1959. This method is called Dijkstra's algorithm.

Dijkstra later said he worked it out at a café in Amsterdam in about 20 minutes, without pencil and paper. OSPF, a system that chooses the routes for data across networks, also uses this method to calculate routes.

PageRank (1998): judging a page's importance from its links

Sergey Brin and Larry Page came up with it as graduate students at Stanford University. They presented it in a 1998 paper, together with a prototype of the Google search engine. The idea is that a page is more important if many pages link to it, especially important pages. According to Google's official guide, today's search ranks results by combining many systems, including PageRank.

RSA (1977): using "hard work" as protection

Rivest, Shamir and Adleman of MIT reported it in 1977, and it appeared in a journal in 1978. Multiplying two large prime numbers is easy. But finding the original two primes from the result takes a very long time with any known method. RSA builds its security on this difference in effort. "What Is Encryption?" explains more.

Maze search (1961): routing the wires on a chip

In 1961, C. Y. Lee published a method for finding a path that connects two points while avoiding obstacles. Starting from the start square, it numbers the neighboring squares, then their neighbors, spreading out like a wave. When the numbers reach the goal, it traces them back to the start. Design software that decides the wiring on circuit boards and semiconductor chips automatically has long used methods built on this idea.

Algorithms for chips that work in parallel

It also matters to choose an algorithm that suits the hardware it runs on. A GPU is a chip with thousands or more simple calculation circuits that all run at the same time. To use that power, the steps must be reorganized so they can move forward at the same time.

As an example, take the sum of 1,024 numbers. Adding them one by one takes 1,023 additions, done one after another, each waiting for the previous answer. To do it in parallel, first pair up the numbers and do 512 additions at once. Adding the remaining 512 numbers in pairs again leaves 256. Repeat this, and after the 10th round you have a single total.

Both ways use the same 1,023 additions. What changes is how many times you wait for an earlier answer. Adding in order means waiting 1,023 times, while the parallel way waits only 10 times. A technical document from NVIDIA, a GPU maker, also presents this tree-shaped adding as the basic pattern for summing many numbers on a GPU.

On the other hand, steps that cannot move on without the previous result are hard to run in parallel. Binary search is a typical example, because the result of each comparison decides where to look next. "Why Are GPUs Used for AI?" explains why AI calculations suit this kind of side-by-side work.

Common misconceptions

By the numbers

The counts above are estimates that assume each comparison takes the same time. Real times also depend on things like how fast data can be brought in from memory.

Learn more

• Try it: the sorting algorithm visualizer, the time complexity (Big-O) comparison tool, the Dijkstra's algorithm calculator and the binary search tree and heap visualizer
• Compare in a table: BFS vs. DFS, array vs. linked list, CPU vs. GPU
• Terms for your next step: stable sort, recursion, hash table, greedy algorithm, dynamic programming
• Read the basics: "What Is a CPU?", "How Compilers Work", "Why Are GPUs Used for AI?"