Рекуррентное соотношение алгоритма сложности

Question

int function(int n){
if (n<=1)
 return 1;
else 
 return (2*function(n/2));
}

Каково рекуррентное отношение T(n) для времени выполнения и почему?

Answer 1

Функция сложности этого алгоритма будет

T(n) = T(n / 2) + 1
T(1) = 1

Применяя мастер-теорему, получим

a = 1
b = 2
c = 0 (1 = n^0)

log b(A) = log2(1) = 0 = 0 c, thus case 2
apply values and the result is O(log n).

Как уже правильно сказал @guillaume, это можно решить намного проще, используя линейную функцию.

Answer 2

Вы можете рассчитать напрямую: это ближайшие 2^n, наибольшее или равное.

Вы вычисляете L=log2(n), и вы берете 2^L или 2^(L+1)

Сложность O(log2 N): log2 N операций.