Search code examples
algorithmmathcomplexity-theoryrecurrencemaster-theorem

complexity algorithm recurrence relation

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

What is the recurrence relation T(n) for running time , and why ?

Solution

  • The complexity-function of this algorithm would be

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

    Applying the master-theorem, we would get

    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).

    As @guillaume already correctly stated, this can be solved a lot easier by using a linear function though.