Если у нас N документов, в каждом из которых в среднем по W слов, и в итоговом индексе M уникальных слов, то сложность составления словаря O(N*W*log(M)) в предположении, что время на добавления нового слова не зависит от уже имеющегося размера словаря, а поиск по словарю занимает log(M).