# what is definition of algorithm in computer science? [duplicate]

I have problems in writing algorithms before writing code for a particular program.

An algorithm is just like a recipe.

But when it comes to programming complex structures (like nested conditional statements and loops) in my code, I am not able to write one, and often get confused easily. How can I get over this thing?

• Are you familiar with pseudocode? – Andrew Nov 11 '16 at 3:41
• There is a question in the title, but the body of your post is different (it does not contain question). It is unclear what the answer should look like and how can we help. – Evil Nov 11 '16 at 6:22

## 1 Answer

An algorithm is, alas, an informal concept, which can not have a precise mathematical definition. One can still attempt at an informal definition, and argue that it conveys the right (informal) intuition.

Because of its informal nature, sometimes it's also easy to argue against a given definition, attacking the definition wording. For instance, I've read more than once that an algorithm is a "sequence of steps" which makes my eyebrows raise, since it suggests that any algorithm will always halt within those number of steps, no matter how large the input is. Once, I had a conversation with a physicist where I couldn't follow their argument, and it turned out they identified "halting algorithm" with "constant-time algorithm" since they believed the number of steps were fixed by the algorithm (hence independent from the input).

If I had to define an algorithm, very informally, I would say that it is an informal but unambiguous description that, to each input, it associates a finite sequence of elementary computation steps which can be used to obtain the desired output.

This is far from being perfect. For instance, what is a "elementary computation step"? Further, it does not express that the mapping form input to the sequence of steps must be effective -- otherwise we could associate to all halting TM encodings the steps print 1, and print 0 otherwise.

To fix these issues, I believe that we also need to convey the notion of computability in some way, which is however too much for that definition. One could refer to a specific formalism or programming language, but I'd want that definition to be computation-model-agnostic.

Indeed, one could say that an algorithm is an informal description of, say, a Java program, which is not as detailed as real code, yet is enough detailed that it could be turned into actual Java without needing to do further research, but only doing "coding". I would regard such a definition as quite inelegant, though.

• "An algorithm is, alas, an informal concept, which can not have a precise mathematical definition" -- that is patently wrong. There are plenty of formal definitions of algorithms. – Raphael Nov 11 '16 at 12:49
• @Raphael I believe formalized algorithms are best called programs (if in a language) or machines/automata/whatever, or something else. IMO, the most common use of the term "algorithm" is the common idea which underlies e.g. a Java program, a TM, a lambda-term, ... all of which implement said algorithm. – chi Nov 11 '16 at 16:12
• – Andrew Nov 11 '16 at 23:32
• @AndrewMacFie Maybe we are arguing about different questions. I'm completely convinced that one can formally express/define an algorithm using a TM, ASM, lambda-term, Java program, .... I however believe that there is no widely accepted, formal definition of "algorithm" on its own, independent of the chosen formalism. I mean a definition such as: an algorithm is a tuple $(X,Y,Z)$ where $X$ is a set of ... etc. Quicksort is the unique triple ... and mergesort is the unique triple ... – chi Nov 12 '16 at 0:28