How to find Big O of a dividing recursive function

user_14370636 0
Viewed 119

I am learning Big O and am stuck on a problem.

Problem -

int sample_function (int x) {
 if (x<1){
   return x;}
  
 int y = x/2; 
 return sample_function (y) + sample_function (x-y);
}

What will the big O be if we call 2 recursive calls of (n/2)? I know that Big O of a dividing recursive function (n/2) is O(log(n)) but not sure about this problem.

big-o
3 Answers

The solution to the recurrence relation

T(n) = T(ceiling(n/2))+T(floor(n/2)) + O(1)

is

T(n) = O(n).

This can be proved by induction on n. The inductive basis is straightforward. As for the induction step, let c be a positive constant such that T(ceiling(n/2)) and T(floor(n/2)) are upperbounded by c * ceiling(n/2) and c * floor(n/2), respectively. Thus, T(n) is upperbounded by c * (ceiling(n/2) + floor(n/2) = c * n.

user_147629210

Dividing an integer x by 2 to reach 0 takes roughly log2(x) steps. Each step doubles the number of function calls. For example:

  8
  4               4
  2       2       2       2
  1   1   1   1   1   1   1   1
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

In total thats sum( 2^k ), k = 0 ...log2(x) = O(x).

For 0 and negatives you return on the first call, thats O(1).

PS: One can argue that the function is actually O(1). A compiler might replace it with:

int sample_function (int x) {
    if (x < 1) return x;
    else return 0;
}
user_41177280

T(n) = 2 * T(n / 2) + O(1) = 4 * T(n / 4) + 2 * O(1) = 8 * T(n / 8) + 4 * O(1) = ... = n * O(1) + (n / 2) * O(1)

So, it's O(n).

user_59231390
Related