Analyze the following algorithm int fooint n int left int ri

Analyze the following algorithm int foo(int n, int left, int right) {int rVal = 0; for (int i = 0; i 2) {int mid = left + (right - left)/2; return foo(n, left, mid -1) + foo(n, mid + l, right);} return 1;}

Solution

The code can be analyzed in two parts :

1> the first for loop which runs from 0 to n-1, that is, it runs for n times. Thus the runtime complexity is O(n).

2> second part can be a little confusing. For simplicity, let the initial difference between \'left\' & \'right\' value is n.
     Now, as we can see, code is calculating the middle value, thus dividing the code into two recursive calls equally.

     so the total time for the function can be expressed as :    
                                         T(n)= T(n/2) + T(n/2) + O(1)           { O(1) is a constant time for addition }
                            therefore, T(n)= 2T(n/2) + O(1)
   Solving using Master\'s Theorem,
                    Apply Master theorem case c<log{b}a where a = 2 , b = 2 , c = 0
     Therefore, the runtime complexity is O(n).

So, overall complexity of the code is O(n)+O(n)= O(n)