3 ms·
The paper mentions an algorithm published in 1980 is O( (n/log(n))^2 ), which is better than the Wagner-Fischer algorithm mentioned in the article, even if it's
by judemelancon 11y ago
The paper mentions an algorithm published in 1980 is O( (n/log(n))^2 ), which is better than the Wagner-Fischer algorithm mentioned in the article, even if it's not strongly subquadratic.
- Retric 11y agoO( (n/log(n))^2 ) > 0(n^1.99999999999999) for sufficently large N
- judemelancon 11y agoYes, the fact it's >O(n^k) for all k in [1,2) is why it's not strongly. It's still less than O(n^2).