В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.
Расход памяти ==Минусы алгоритма Фарача== Данный алгоритм является больше теоретическим, нежели практическим. Как можно было заметить, основная идеяалгоритма довольно проста и понятна. И хоть он и является асимптотически оптимальным, на построение дерева практике его используютдовольно редко. Это связано с тем, что алгоритм весьма сложен для реализации, по сравнению с другими алгоритмамипостроения суффиксы деревьев, а также линеен(т.к на каждой фазе мы лишь строим и сливаем сжатые суффиксные деверья)требует достаточно большой объем памяти.
==См. также==
