# How different algorithms are developed? [closed]

Preamble: This is a very general question, which I have always been wondering about. I understand there might not be well formulated way of developing algorithms I just would like to seek and see different opinions on this.

The reason I am posing this on MATHEMATICS stack exchange is because I feel some how it relates to the difference between applied and pure mathematics.

Question: It seems developing different algorithms (techniques) to find a solution of a problem is normally done via trial and error, and sometimes based on some intuitions, but it never involves as much rigor as pure mathematics does. Take the techniques to find the solutions of polynomial equations for example. These were found and used by early mathematicians way before the establishment of modern rigorous mathematics (history of solution of polynomial equations).

Or another example could be the ML estimator which was used way before axioms of probability was proposed by Kolmogorov. It is a very intuitive thing that we take the maximum of probability distribution of the observation as an estimate of the desired parameter. ML might have been studied more rigorously in modern probability theory by now though.

Or even some methods and techniques used in calculus like integration, where they have their roots in ancient Greek mathematics. Again way before calculus was formally studdied.

So the question is that: is this same approach used today by modern mathematicians to develop techniques based on intuition and trial and error Or is there a more formulated way to find solutions and develop algorithms?

Finally, does the pure mathematics tells us something or show us something (for example a polynomial equation has a solution) and then is the purpose of applied mathematics (or engineering) to find solution and algorithms using experimentation?

## closed as off-topic by Andrés E. Caicedo, user91500, Daniel W. Farlow, Glorfindel, user370967 Jul 4 '17 at 15:47

This question appears to be off-topic. The users who voted to close gave these specific reasons:

• "This question is not about mathematics, within the scope defined in the help center." – Andrés E. Caicedo, Glorfindel
• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user91500, Daniel W. Farlow
If this question can be reworded to fit the rules in the help center, please edit the question.

• The field "pure mathematics" is too broad to compare it to the way algorithms are found. For example, many methods in algebra and number theory start as algorithmic approaches, whereas in other parts of mathematics, the relation between the two topics can be much thinner. – Dirk Jul 4 '17 at 7:37

## 2 Answers

Finding relations and altorithms for computation can be automated with computer algebra systems in many ways. One example are lattice reduction algorithms and integer relation algorithms (PSLQ for instance).

Most of the times, automated search is still brute-forcing (search through a tree of all possibilities). I'd say at the end it's still mostly inspiration and trial and error, but the process of checking and searching can be systematic.

A different reasoning: if an algorithm, formula or a proof, is derived by following an established formal procedure, it's not actually new, even if it hasn't been derived before. Such results don't require a living mathematician to be derived, just sometimes a lot of routine effort. An "inspiration" will always be needed for truly new results (that's what discovery is all about, otherwise we're just reinventing the wheel). That's not to say that this "inspiration" can't be done with AI.

On top of a possible lack of rigour, another important ingredient that was also probably missing to ancient mathematicians is the analysis of the complexity of an algorithm. Of course, there was a very convincing measure of complexity: the time required for a computation by hand. A typical example is the chase for prime numbers before (and even after) the computer area, which includes more and more sophisticated primality tests.

Coming back to your question "is there a more formulated way to find solutions and develop algorithms?", the answer is definitely yes and this is a major branch of computer science. I refer you to the "See also" section of Analysis of algorithms, but to keep this answer at an elementary level, I would just like to mention two emblematic examples (there are many more!).

The first one are the sorting algorithms, which were studied from the 1950's. There were several known algorithms in time $O(n^2)$ in the fifties and the discovery of the $0(n\log n)$ algorithm QuickSort by Hoare in the early 1960's was a real breakthrough. The rigorous analysis is performed by counting the number of comparisons in average.

The second one is the notion of hash table, which essentially consists in assigning a numeral key to an object to make searching easy. Possibly using improvements like double hashing, one can achieve incredible efficiency: arbitrary insertions and deletions can be performed at constant average cost per operation. The design and analysis of this type of algorithm makes use of probability and prime numbers.

Other famous examples include cryptography (where prime numbers also play a central role) and graph algorithms.