Как найти временную сложность следующего кода?

Question

Не могли бы вы объяснить, как найти временную сложность следующего кода? Любая помощь оценивается.

int boo(n) { 
    if (n > 0) 
    { 
     return 1 + boo(n/2) + boo(n/2); 
    } 
    else 
    { 
     return 0; 
    } 
} 

Answer 1

Иногда это хорошо, чтобы записать его. Когда вы начинаете, он суммирует 1 + boo (n/2) + boo (n/2), который находится во второй строке.

И каждый из этой п/2 выполняется также

и т.д. и т.п.

Таким образом, в конце концов, в то время как количество звонков растет exponencially, число repetions только logharitmic, который в конец удаляет друг друга, и вы получаете O (N).

PS: Достаточно подсчитать последнюю строку, у всего дерева всегда только один раз больше узлов (минус один), которые по теории сложности небрежны (вам не нужны константы, которые умножаются на два)