Algorithm

An algorithm is a step-by-step process for solving a problem or performing a calculation. In mathematics and computer science, algorithms are like recipes that tell a computer or a person exactly what to do, step by step, to get a result. They can guide everything from simple math problems to complex tasks like organizing data or playing games.

Algorithms are important because they help us solve many kinds of problems quickly and accurately. They are used in almost every part of modern life, from the way search engines find information to how credit cards process payments. Some algorithms can even make decisions for us, like choosing what videos to watch next or what products to buy.

Not all methods for solving problems are algorithms. Some, called heuristics, are guidelines or rules of thumb that help us make decisions but don’t always give the perfect answer. For example, recommender systems on social media use heuristics because there isn’t one single “right” answer for what someone should see next.

An algorithm must finish in a finite amount of time and space. This means it can’t go on forever or need an endless amount of memory. Some algorithms are deterministic, meaning they always give the same result for the same starting point. Others are randomized algorithms, which use some randomness to explore different possibilities and often find better solutions.

Etymology

The word "algorithm" comes from the name of a Persian scientist, Muḥammad ibn Mūsā al-Khwārizmī, who wrote important books about math around 825 AD. When his works were translated into Latin in the 12th century, his name was changed to "Algoritmi." This is how the word algorism entered English, meaning a method of doing calculations with place-value numbers. Over time, the word evolved into "algorithm," which we use today to describe step-by-step processes in math and computer science.

Definition

An algorithm is a set of rules that clearly describes a sequence of steps to follow. This can include things like computer programs, instructions for completing a task, or even a recipe for cooking. For an algorithm to work properly, it should eventually come to an end, although sometimes people might want steps that go on forever.

History

Step-by-step methods for solving math problems have been used since ancient times. For example, people in Babylonian mathematics, Egyptian mathematics, and Greek mathematics created rules to help with calculations. One early example is a Sumerian clay tablet from around 2500 BC that shows a method for division.

Later, mathematicians like Muḥammad ibn Mūsā al-Khwārizmī created clear, step-by-step ways to solve problems. His work helped turn math into a process with set rules, which is a key idea behind modern algorithms. Today, algorithms are used in many places, like social media apps such as Instagram and YouTube, to help decide what you see based on what you like.

Representations

Algorithms can be written in many different ways, such as using everyday words, special code called pseudocode, diagrams called flowcharts, or even computer languages. Each way has its own benefits; for example, flowcharts use simple shapes and arrows to show the steps clearly.

One special way to think about algorithms uses something called a Turing machine, which is a model for how computers might work. These algorithms can be described in simple terms, in more detailed steps, or in very exact rules. Flowcharts are especially helpful because they use easy-to-understand symbols to map out the process of an algorithm.

Algorithmic analysis

Main article: Analysis of algorithms

We often want to know how much time or space an algorithm needs to do its job. Scientists use special ways to guess these needs. For example, adding numbers in a list might take time that grows with the list size, shown as O(n). Sometimes, different ways to solve the same problem can be faster or slower. A smart search method can be much quicker than a simple one when looking up items in a big list.

Scientists study algorithms in two ways: by math and by testing. Math helps understand what an algorithm can do, while testing shows how it works in real life. Even small changes can make big differences, especially for jobs that need to be done very fast, like in medical pictures. Every algorithm has a best case (when it works fastest) and a worst case (when it takes the most time).

Design

Algorithm design is a way to solve problems by creating step-by-step instructions for computers to follow. It is part of many problem-solving methods, like breaking big problems into smaller ones (divide-and-conquer) or saving steps to use less memory and time (dynamic programming). One key goal is to make sure the algorithm works well even with big amounts of data, which is often measured using something called big O notation.

Structured programming helps make algorithms easier to understand and check. Even with just a few basic instructions, like making choices and repeating steps, programmers can create clear and correct programs. This structure helps avoid messy code and makes it easier to prove that the algorithm works as intended.

Legal status

See also: Software patent

Algorithms by themselves are generally not patentable. In the United States, simply manipulating abstract ideas, numbers, or signals is not considered a patentable "process." However, practical uses of algorithms can be patented. For instance, using an algorithm to help cure synthetic rubber was approved as patentable. The patenting of software remains a debated topic, especially regarding algorithms used for tasks like data compression. Some cryptographic algorithms also face export restrictions.

Classification

Algorithms can be grouped in different ways based on how they work. One way is by how they are implemented. Some algorithms use a method called recursion, where the algorithm calls itself repeatedly until it reaches a stopping point. Others use iteration, which involves repeating steps using loops or data structures like stacks. For example, the Tower of Hanoi puzzle can be solved using recursion.

Algorithms can also be deterministic, meaning they make exact decisions at each step, or non-deterministic, where they make guesses that get better with heuristics. Some algorithms find the exact solution, while others, like approximation algorithms, look for answers close to the correct one. For instance, the Knapsack problem tries to fit items into a bag without exceeding a weight limit, balancing value and weight.

Another classification is by their design paradigm. Brute-force methods try every possible option until they find the best solution. Divide-and-conquer breaks problems into smaller parts, solves each part, and then combines the solutions—like in merge sorting, where a list is split, sorted, and then merged back together. Randomized algorithms make random choices to find solutions, which can be faster for some problems.

For optimization problems, algorithms can use methods like linear programming to find the best solution under certain conditions, or dynamic programming to break problems into overlapping subproblems and store solutions to avoid repeating work. Greedy algorithms build up a solution step by step, often finding a good but not perfect solution. Heuristic algorithms approach the optimal solution over time and include methods like local search and genetic algorithms.

Examples

Further information: List of algorithms

One of the simplest algorithms is used to find the largest number in a list of numbers. To do this, you look at every number in the list. Start by assuming the first number is the largest. Then, compare each remaining number to the current largest. If you find a number that is bigger, it becomes the new largest. Keep doing this until you've checked all the numbers. The last number you marked as the largest is the actual largest number in the list.

This process can be described more formally, almost like giving instructions to a computer, using special ways of writing called pseudocode or pidgin code.