>>O(n^2)

O(n * размер алфавита), где n - длина слова

>>Dictionary
не знаю точно ничего про этот класс, но рискну предположить, что реализован он как дерево, поэтому поиск вроде containsKey и тп работает за log. И это не считая того, что сам класс, естественно, сильно запутан в целях универсальности.
ИМХО, в таких случаях надо делать как-то так (сорри, но на сях):
Так O(1), а памяти на алфавит не очень жалко.

__________________
Bedankt euch dafür bei euch selbst.

H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ