Евклид против Берлекэмпа-Месси

[vlad_light]

Кто подскажет, какая (асимптотическая) сложность у данных алгоритмов (в зависимости от входных данных) при декодировании кодов Рида-Соломона?
У Блейхута, вроди, написано, что Евклид имеет сложность $O(n\ln ^2 n)$, а Берлекэмп-Месси - $O(n^2)$. Но везде написано, что алгоритм БМ работает быстрее. Наверное, я что-то не так прочитал... Подскажите, пожалуйста, очень нужно! Спасибо!