Какова временная сложность string.GetHashCode?

Question

Какова временная сложность метода String.GetHashCode()? Например, если хешированная строка длины n, от mod 2 используя схему Хорнера это O(n), Что такое Big O для GetHashCode?

Answer 1

Согласно справочному источнику временная сложность составляет O(n). В основном он берет каждый символ строки и добавляет его значение в хеш.

Как упомянуто в комментарии Питера Ричи, алгоритм можно изменить, следуя инструкциям на http://msdn.microsoft.com/en-us/library/jj152924(v=vs.110).aspx.