Как определить рекуррентное соотношение, описываемое эффективностью этого кода

Question

Я новичок в алгоритме анализа. Я нашел этот код в сети

boolean p (int s, int t, int n){
    if (n == 1) {
        if e(s, t) 
            return true;
        else
            return false;
    }
    else {
        for(i = 1; i <= n; i++) {
            if (p(s, i, n/2) and p(i, t, n/2))
                return true;
        }
    }
    return false;    
}

Как определить отношение повторения, описываемое эффективностью этого кода?

Предположим, что функция e(i, j) возвращает логическое значение и принимает O (1 )

Answer 1

Чтобы выяснить рекуррентное отношение в терминах n , рассмотрим следующий фрагмент кода.

for(i=1;i<=n;i++) 
{
    if (p(s,i,n/2) and p(i,t,n/2))
        return true;
}

Мы видим, что l oop выполняется n раз. Обратите внимание, что l oop не зависит от параметров s и t .

Во время каждого выполнения этот l oop дважды вызывает функцию p() с параметром n / 2 .

Также обратите внимание, что другие операции, включая функцию e(i,j) занимает только постоянное время.

Таким образом, рекуррентное отношение проблемы равно T(n) = 2n T(n/2) + O(1).