# What is an algorithm?

What exactly is an algorithm, as in what does Algorithm mean? The little I understand the word, is that it's not specific to a particular language, or design pattern, rather it's one the most basic principles (so I guess this question makes me look stupid).

One of the "options" I have of understanding it, is that it means the method of getting something done, that could be written as a list in pseudocode.

When I write more complicated code, I think what needs to be done, with what, and how I would get there (not in a programming language), then write that in code. Is that good way to go about it, and is that anything to do with algorithms?

(I wanted to ask here rather on Stackoverflow, because it's not about a specific problem/language plus I get the feeling that the majority of people here know the 'why', or at least the answers here are more detailed, rather than on Stackoverflow where it's different, I'm sorry if I should have asked over there)

-
Google? Wiki? google.com/search?q=algorithm – Maglob Apr 17 '11 at 21:28
Not quite as useful, or easy to understand as here. Wikipedia wasn't that useful to me at least. – Jonathan. Apr 17 '11 at 21:30
An algorithm is the description of thhe set of steps to take to solve a problem within known and limited resources and time. Anything else is a procedure or maybe an heuristic. – Apalala Apr 17 '11 at 21:53
@Apalala: I don't think those limitations apply. – Josh K Apr 17 '11 at 23:32
@Apalala: Finite, not known. – Josh K Apr 18 '11 at 1:37
show 9 more comments

## 11 Answers

An algorithm is a finite sequence of well-defined instructions for calculating a function (or executing a procedure) that terminates in a well-defined ending state.

-
 +1. "Finite, Well-Defined and Effective" are the three criteria in the Wikipedia entry. You have all three here, also. – S.Lott Apr 18 '11 at 10:32 I'm set up to watch the videos quoted by @Jörg, but my current point of view is that not only the steps must be finite. If the resources (including time) are not bounded, then the procedure can be called or labeled as anything, but not an algorithm. – Apalala Apr 18 '11 at 18:13 @Apalala - I've been going back through my textbooks, and I don't see that restriction anywhere. It's possible that for a particular data set or input an algorithm may not terminate (algorithms like the Newton-Raphson method for finding a root may get stuck in a never-ending loop), but that doesn't make the algorithm not an algorithm. – John Bode Apr 18 '11 at 20:15 @John Oscillations can and routinely detected in Newton-Raphson. – Apalala Apr 21 '11 at 18:42 @John This is the definition of algorithm in this 1983 book: goo.gl/uwNr2. ...is a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time.. – Apalala Apr 21 '11 at 18:47
show 2 more comments

This is actually a pretty interesting question, and in fact still an open research question.

Yuri Gurevich, one of the giants of Algorithm Theory, is currently giving a video lecture series on Microsoft's community website Channel9:

As you can see, your very question is actually the title of the second lecture. However, I would strongly suggest you watch all three of them.

The first one, in particular, contains a couple of examples of algorithms that invalidate pretty much all of the definitions given in most of the other answers here.

-

An algorithm is a set of rules or process (in a calculation) used for problem-solving. Basically, there's a problem, you want a solution, and the process to this solution is an algorithm. An algorithm has a finite sets of rules/process to reach to a solution.

If you're like Edsger W. Dijkstra, you will write your algorithm on a piece of paper and work out/refine the algorithm on paper till you're satisfied about your algorithms. Otherwise (especially when writing documentations), a flowchart is used to diagrammatically represent the flow of an algorithm/process. This allows for others to critique the flowchart and improve if need be (without worrying about what programming language is needed).

I don't know if that answers your question.

-
 I don't like the word set because it means "not ordered". I'd prefer "sequence", or event tuple to stay in math area – Ubiquité Apr 17 '11 at 21:29 @Ubiquité, Set doesn't necessarily mean "not ordered". You can classify a set in the ordering you want (e.g. a random ordering). Still, that doesn't require a downvote because of people's interpretation of the word "set". Plus, you can have a compound set, which is a grouping of sets, which also is part of the algorithms. Hence "set" can be anything, as long as its appropriately used as an algorithmic solution to a problem. – Buhake Sindi Apr 18 '11 at 8:11 I didn't downvote ! – Ubiquité Apr 18 '11 at 9:03 Sorry, I didn't meant to blame you on the downvote. The downvoter should explicitly provide reasons for the downvote. – Buhake Sindi Apr 18 '11 at 9:42

An algorithm is like a good cooking recipe. You have some inputs, some well-defined intermediate steps and get a final result.

Applied to programming, it's an unambiguous description of the steps you need to do solve a particular problem. Anything that you can write down in the programming language of your choice could be seen as an algorithm - but typically the term is only used for common logical or mathematical tasks, such as sorting or searching.

-
 There are plenty of algorithms that don't necessarily give a final result. An operating system or a web server, for example, is an algorithm for which giving a final result is usually considered a bug. – Jörg W Mittag Apr 21 '11 at 23:37

If I had to give a general definition, I'd say an algorithm is a formula for solving a computing problem that's more complex than, and ends up being more efficient than, the obvious/brute force solution.

Also, it's important to note that an algorithm is not any specific source code; it's the computation itself. Among other things, this means that any Turing-complete language can implement any algorithm that any other Turing-complete language can implement.

-
I liked this answer a lot, and I think we could take it a bit further and say (though not related to the original question): any algorithm is an optimization of a brute force/tree search solution. Was wondering if it can be proven formally. – mojuba Apr 17 '11 at 21:48
-1 "Algorithm" is a well defined mathematical term. – Apalala Apr 17 '11 at 21:50
@Apalala so what stops you from redefining it for the sake of clarity or, say, better understanding of its essence? Algorithm as a "set of instructions" says almost nothing to me. – mojuba Apr 17 '11 at 21:55
@mojuba I really don't care if the term is going to be redefined, but I think that the traditional definition was useful, because it at least differentiated among ways of approaching problems: An algorithm is a recipe for solving a problem using finite resources. Change that definition, and the foreseeable consequence is that we will have to come up with another word that means the same. Darn! All the knowledge gained in the past century about computability and complexity goes away without a sound definition of algorithm! – Apalala Apr 18 '11 at 1:15
@Apalala: If the OP had wanted a dictionary definition, he could have gone to dictionary.com. Instead, he came here, which meant he probably wanted a slightly more in-depth explanation. – Mason Wheeler Apr 18 '11 at 15:15
show 1 more comment

I use the term to describe a formula to solve a specific problem. The formula does not necessarily need to be written in math or have 1:1 relationship with a method. In school algorithms and data structures are closely related and can be written as math formulas or proven using proofs.

-

An algorithm is an abstraction of a computer program, and consists of a set of instructions to achieve some well-defined task in a finite number of steps, though the bound on the step count might be very large and the individual steps might be complex (finite) tasks in their own right. While there are (correct) programs that are overall known-non-algorithmic, they all work by repeating algorithmic pieces in some pattern. (More interesting are the programs whose termination status is not known, but most programmers don't actually deal with such things intentionally; I know I don't!)

-

Algorithm: a well-ordered set of operations that are 1) unambiguous and 2) effectively computable such that executing the operations starting from the first produces a result after a finite number of operations.

-
 Counter example: an operating system. It doesn't produce a result at all, in fact, that is usually considered a bug. – Jörg W Mittag Apr 21 '11 at 23:38 @Jörg, well the OS produces many results that, taken together, produce the overall result of providing system services to applications. – ThomasMcLeod Apr 26 '11 at 1:31

IMO nobody quite knows :) I've seen the term applied only to mathematical calculation functions, to any function that takes input and produces output, and to anything that takes input and performs some kind of operation on it.

Would you consider any/all of the following to be an algorithm?

1. A function that calculates the interest rate of a loan over a period of 20 years
2. Business logic that checks if all information has been entered on a loan application
3. A finder function that queries a database for a Customer object
4. A "helper" function that cleans up and formats data-entry
5. A function that parses an XML file and maps data to business objects
6. A class that takes input and writes them to a text file
-

An Algorithm is an idea, a method, a technique, "smarts" for calculation or execution of a task that is abstract in nature, but as it runs on computers in the real world, we aspire for it to use as little resources as possible, which are, in the computer world, Time and memory.

-

An algorithm is a sequence of well-defined steps that produce a result in finite time.

Well-defined step: That's something you can do, or calculate, that is precisely defined. Just by reading the step you know what you have to do and how to do it. Specifically, you can write it in a programming language you know, and be sure the program fragment matches the step exactly.

Sequence: The steps are executed in an order that is specified. Steps may be executed more than once depending on the data (loops) or not executed at all depending on the data (if statements). Parallel algorithms impose only a partial order on the steps, so I'm oversimplifying here. It would be more correct to describe it as a partially-ordered set than a sequence, but I wanted to keep the words a little simpler. Besides, it's easily possible to embed a partially-ordered set in a full order.

Result: An ending state or value. It doesn't have to be predictable in advance, but it does have to be a definite end satisfying some condition. This does mean that an operating system is not an algorithm, although it uses a whole lot of them.

Finite: An algorithm is guaranteed to stop sometime, at least on a machine that can run long enough. It isn't necessarily guaranteed to stop in a predictable time, and it isn't guaranteed that it would stop before the sun expands and turns red on any existing machine. This also means an operating system is not an algorithm, as ideally it will run forever. I've seen the word "procedure" used to describe something that would be an algorithm if we were sure it would stop sometime. (It is possible to have an algorithm that will stop in an unknown amount of time. Suppose, say Goldbach's conjecture was proved mathematically false, in a nonconstructive proof, so there was an even number > 2 that wasn't the sum of two primes. An algorithm that simply tested even numbers would then eventually terminate, although nobody would know when.)

The algorithm is an intentionally abstract sort of thing, so we don't consider questions like "Is it physically possible to execute this before the heat death of the Universe?". They'd be too hard to answer. If it relates to computer operations, it's easy to implement it in a programming language.

-