Questions tagged [algorithm]
The algorithm tag has no summary.
25 questions
1 vote
0 answers
88 views
Is there any instance of a recursive minimization or maximization function that existed before 1945?
I recently skimmed over Bellman's first paper on dynamic programming and I was wondering if there was any published instance of a recursive min or max function that solved an optimization problem that ...
- 1,547
6 votes
2 answers
885 views
Who first showed the famous best worst case complexity on sorting algorithms?
It is common knowledge that a sorting algorithm based on comparisons cannot have a worst case complexity better than $O(n \log n)$. This can be demonstrated by a counting argument on the number of ...
- 517
1 vote
2 answers
200 views
Who pioneered the use of the Fast Fourier Transform (FFT) for efficient multiplication?
The Fast Fourier Transform (FFT) is an efficient algorithm used in the computation of the discrete Fourier transform. While it's well-known for its applications in signal processing, it has also been ...
- 1,547
3 votes
1 answer
180 views
First use of ~ and ≍ (\sym and \asymp)
The relations ~ and ≍ are frequently used in math and computer science, at least within number theory and analysis of algorithms. What is their origin? Definitions Suppose $g(x)$ is an eventually-...
- 131
3 votes
0 answers
304 views
Who came up with the proof of "Bézout's identity" that uses the well-ordering principle?
Let $a$ and $b$ be two integers not both of which are equal to zero. It is an important and well-known fact that $\text{gcd}(a,b)=ax_{0}+by_{0}$ for some integers $x_{0}$ and $y_{0}$. Even though this ...
- 2,034
1 vote
1 answer
234 views
Did the 1800 Gregorian Lunar Correction Motivate Gauss' Computus Algorithm?
When the Gregorian calendar was implemented in 1582, one of its adjustments was the lunar correction---to increase the epact by 1 eight times within a span of 2500 years; specifically, seven times ...
- 277
3 votes
1 answer
181 views
Where does the term "pivot" come from in the quicksort algorithm?
The quicksort algorithm is based on recursively choosing an element to partition the array. In every modern exposition that I've seen, this element is called the "pivot". However, as far as ...
- 225
4 votes
2 answers
813 views
How did Yao come up with his minimum spanning tree algorithm?
I recently stumbled upon this text about Yao's algorithm for the minimum spanning tree (MST) and I was wondering if there are some preceding algorithms (other than Sollin's algorithm) that were ...
- 1,547