Временная сложность алгоритма, разделение задачи размера (n) на 2 задачи размера (n-1)

Question

Алгоритм B делит задачу на 2 подзадачи размера n-1, решает их рекурсивно, а затем объединяет их за постоянное время.

Какова временная сложность алгоритма B?

Answer 1

попробуйте изобразить вызовы как узлы дерева:
это дерево (двоичное дерево), где обе ветви будут иметь высоту n-1 (из-за рекурсивного вызова с размером n-1), таким образом, узел root будет иметь левую ветвь с высотой n-1 и правую ветвь с высотой n-1. 1006

2^(n-1)      +      2^(n-1)       +       1  
left branch         right branch          root node

= 2 * 2^(n-1) + 1
= 2^n (the +1 is negligible)

Answer 2

В основном мне кажется:

                 n                     layer 0        
              ／    ＼                 
           ／          ＼             
        (n-1)          (n-1)           layer 1
       ／   ＼        ／   ＼          
    (n-2)   (n-2)  (n-2)   (n-2)       layer 2
     / \     / \    / \     / \
   ..............................        ...
   | | | | .............. | | | |
   1 1 1 1                1 1 1 1      layer n - 1

Высота (количество горизонтальных слоев) n, и каждый слой i выполняет 2^i операций, поэтому сложность:

2^0 + 2^1 + ... + 2^(n - 1) = 
∑ 2^i [i = 0, ..., n - 1] =
2^n - 1

Итак, O(2^n - 1) = O(2^n).