Часть 2: Доказательство Итак, как мы видели в Части 1 и поняли концепцию рекуррентного отношения. Теперь мы готовы понять, как работает основная теорема. Напомним, в предыдущем посте мы определили что а как количество повторений, b как коэффициент, на который мы делим наш ввод, d степень сложности, до которой выполняется работа вне повторений, а n — это размер ввода. Мы также определили, что у нас обычно есть aʲ количество подзадач, каждая из которых имеет размер n/bʲ..