Моё знакомство с теорией сложности ограничивается лишь Корменом, так что может вы подскажите, доказательство какого результата требует навыков раскрывать неопределенности?
Доказательство любой оценки по "о-большому". Неопределённость
Вообще-то
это когда отношение
ограничено, и как раз в теории сложности встречаются случаи, когда предела у этого отношения нет. Лопиталь там не нужен, там нужны оценки, решение рекуррентных уравнение (линейных рекуррентностей с постоянными коэффициентами и мастер-теоремы для большинства случаев достаточно) и умножение О-больших.
Я могу доказать что пи-функция (КМП-алгоритм) работает за
не использовав ни разу раскрытие неопределенностей
Скорей всего, потому, что забыли, как это доказывается.
Лопиталей там нет, там оценка числа итераций цикла.