Landau-Symbole
Another notable example is the algorithm invented by Anatolii A. Karatsuba in 1960 that could multiply two "n"-digit numbers in formula_1 operations (in Big O notation). This algorithm disproved Andrey Kolmogorov's 1956 conjecture that formula_2 operations would be required for that task.