12

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)

Improve this question
14
  • 5
    Google? Wiki? google.com/search?q=algorithm
    – Maglob
    Apr 17, 2011 at 21:28
  • 1
    @Apalala: I don't think those limitations apply.
    – Josh K
    Apr 17, 2011 at 23:32
  • 2
    @Apalala: Finite, not known.
    – Josh K
    Apr 18, 2011 at 1:37
  • 2
    @Jonathan: "words that I have to look up"? Which words? Be specific. This site is not magic. We don't know you. We don't know what you read. We don't know what confused you. Please be specific.
    – S.Lott
    Apr 18, 2011 at 10:19
  • 1
    @Apalala: "Finite" means "bounded", nothing more. An algorithm is guaranteed to stop sometime. It's much easier to prove finiteness when you have some sort of way of predicting it will end, so algorithms tend to be predictable, but predictability is not in the usual definition of algorithms.
    – David Thornley
    Apr 22, 2011 at 15:01

12 Answers 12

Reset to default
19

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.

Improve this answer
7
  • 1
    +1. "Finite, Well-Defined and Effective" are the three criteria in the Wikipedia entry. You have all three here, also.
    – S.Lott
    Apr 18, 2011 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, 2011 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, 2011 at 20:15
  • @John Oscillations can and routinely detected in Newton-Raphson.
    – Apalala
    Apr 21, 2011 at 18:42
  • 1
    @Apalala: that sounds more like the definition of a program than of an algorithm. This idea of discrete steps is present in Turing machines, register machines, random-access machines, and of course in our actual physical computers, also in pretty much every programming language and even, albeit more implicitly, in lambda calculus. But that is an arbitrary restriction that is not inherent in algorithms. Analog algorithms, for example, do not have discrete steps (in fact, that is the definition of an analog algorithm), and they can actually be implemented with an analog computer.
    – Jörg W Mittag
    Apr 21, 2011 at 23:35
15

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.

Improve this answer
3
  • 2
    Thanks for the links. You'll notice the following in the text that accompanies the first video, as a part of the definition of an algorithm: "eventually terminating in a final ending state". Termination is an essential part of the definition of an algorithm. That's why operating systems and non-terminating servers are not algorithms.
    – LIProf
    Sep 6, 2017 at 22:54
  • @LIProf: Unfortunately, the marketing blurb does not really do the series justice. In fact, literally the very first example given in the very first video, less than 3 minutes in, is of an algorithm that does not always terminate: the geometric interpretation of Euclid's Algorithm, i.e. the way that Euclid originally formulated it, finds the longest common measure of two line segments, but only if the two lines segments are commeasurable (IOW, only if there exists a common measure at all).
    – Jörg W Mittag
    Jul 24, 2021 at 8:19
  • And about 16 minutes into the second lecture, Gurevich lists a couple of examples of algorithms, and explicitly lists an Operating System as an example of an algorithm. Another pretty famous algorithm that does not always terminate, is Dijkstra's Algorithm for finding the shortest path in a graph, which may give a wrong answer if there are edges with negative weight, and will not terminate at all if there are cycles with negative weight (because you can always make the path shorter by going round the cycle an additional time).
    – Jörg W Mittag
    Jul 24, 2021 at 8:26
4

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.

Improve this answer
2
  • 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, 2011 at 23:37
  • @JörgWMittag but is an OS or a web server "an algorithm"? I think they aren't -- they may solve subproblems of their domain using algorithms -- and in every case, they definitely need a final result -- but they also have parts that aren't algorithms, and as a whole they aren't algorithms. (It's like you said in another comment -- OSes and web servers are programs but not necessarily algorithms).
    – Andres F.
    Jan 21, 2020 at 17:48
2

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.

Improve this answer
4
  • I don't like the word set because it means "not ordered". I'd prefer "sequence", or event tuple to stay in math area
    – BenjaminB
    Apr 17, 2011 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, 2011 at 8:11
  • I didn't downvote !
    – BenjaminB
    Apr 18, 2011 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, 2011 at 9:42
1

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.

Improve this answer
3
  • 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, 2011 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, 2011 at 1:31
  • @JörgWMittag Like I said in other comments to you, a conclusion to your observation would be that an operating system is not, in fact, an algorithm ;)
    – Andres F.
    Jan 21, 2020 at 17:52
1

Algorithm It is the combination of sequential steps (these steps can be calculations, data processing, and reasoning tasks) use to resolve a problem in a very simple and efficient way.

It is designed most efficiently that it can be expressed within a finite amount of space and time. we can implement it in any programming language.

Properties of an algorithm : following are the main properties of an algorithm:-

An algorithm must have a unique name. It should have explicitly defined sets of inputs and outputs. An algorithm must be in sequential order with unambiguous operations. It must have some endpoint, i.e., it halts in a finite amount of time. click here to learn about Design and Analysis of Algorithm

Improve this answer
0

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.

Improve this answer
0

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

Improve this answer
0

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
Improve this answer
0

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.

Improve this answer
0

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.

Improve this answer
-1

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.

Improve this answer
6
  • 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, 2011 at 21:48
  • -1 "Algorithm" is a well defined mathematical term.
    – Apalala
    Apr 17, 2011 at 21:50
  • 1
    @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, 2011 at 21:55
  • 1
    @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, 2011 at 1:15
  • 1
    A brute force search is an algorithm. It isn't generally a pretty algorithm, and isn't generally worth writing up. I don't see any real usefulness in excluding brute force, and in many cases it's not clear what "better than brute force" actually means.
    – David Thornley
    Apr 22, 2011 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.