Изменения

:Итак, алгоритм Куна можно представить как серию из <tex>n_1</tex> запусков обхода в глубину на всём графе.

:Следовательно, всего этот алгоритм исполняется за время <tex>O(nm)</tex>, где <tex>m</tex> {{---}} количество ребер, что в худшем случае есть <tex>O(n^3)</tex>.

:Более точная оценка:

:В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1m)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2)</tex>, где <tex>n_2</tex> — число вершин второй доли.