# Tag Info

## Hot answers tagged lower-bounds

Accepted

### Least number of comparisons needed to sort (order) 5 elements

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance. ...
• 71k
Accepted

### How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

This is a classical result of Winograd: On multiplication of 2x2 matrices. Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix ...
• 270k