Will a sorting algorithm faster than n*log(n) be found before 2030?
19
1kṀ1492
2029
9%
chance

If it only works on quantum computers - it is enough for YES resolution.

The time complexity should be less than O(n*log(n)).

As people hint I am bad at market creation here are the additions made after opening:

  • The algorithm has to be implemented by 2030, not just "be proven to exist". Proving the existence is not "finding".

  • The worst time of the new questioned algorithm has to be better than O(n*log(n)) for a YES resolution.

  • The market closes at the end of 2029 and resolves at the start of 2030.

  • The intended field of interest of the question was about whether quantum computers or related technologies would give any improvement. Not about whether there are datatypes which are easier to sort.

  • I will not resolve this question by myself, as I am not qualified to evaluate the results of work in quantum physics. I will not bet.

Technology
Computational Complexity Theory
Get
Ṁ1,000
to start trading!

People are also trading

Does there exist a sorting algorithm with average time complexity better than O(n * log(n)) on a list of integers?
97% chance
Will a polynomial time factoring algorithm be found by 2035?
9% chance
Will an algorithm be able to work on million-line codebases before 2026?
37% chance
Will a polynomial-time algorithm for an NP-complete problem be published by 2030?
4% chance
Will the Collatz Conjecture (3x+1 problem) be solved before 2030?
15% chance
Will go be solved before 2040?
6% chance
Will "Genetic Algorithm" come back before 2031?
39% chance
Will Nonlinear exist in 2030?
36% chance
By 2028, AI can learn to efficiently sort lists of numbers much larger than in any training set used
85% chance
Will Goldbach's conjecture be proved before 2030?
23% chance
© Manifold Markets, Inc.•Terms•Privacy