CYK algorithm: Difference between revisions

Revision as of 11:03, 27 February 2010

Revision as of 11:15, 27 February 2010

Line 77:

as the CYK algorithm; yet he showed that Boolean [[Matrix multiplication#Algorithms for efficient matrix multiplication|matrix multiplication]] can be utilized for performing this computation.

Using the [[Coppersmith–Winograd algorithm]] for multiplying Boolean matrices, this gives an asymptotic worst-case running time of <math>O(n^{2.38} \cdot |G|)</math>. However, the constant term hidden by the [[Big O Notation]] is so large that the Coppersmith–Winograd algorithm is only worthwhile for matrices that are too large to handle on present-day computers.<ref> (Knuth, 1997</ref>).

==See also==