Time complexity!

Question

 void find (int n) {
    if (n < 2) return;
    else {
        sum = 0;
        for (i = 1; i <= 4; i++)
            find(n / 2);
        for (i = 1; i <= n*n; i++)
            sum = sum +1;
    }  
     
 }

assume that the division operation takes constant time and sum is global variable. what is the time complexity of find(n)?

Answer 1

Recurrence equation:

T(n)=4T(n/2)+n^2

solving this we get

T(n)=O(n^2 logn )(master theorem case 2)

Comments

If we count the no of function calls ...that would be 4^logn=n^2 (complete 4-ary tree)....and for every function call one for loop of n^2 time complexity...then the total would be O(n^4).

Please help me on this thought.

Answer 2

You can do this question with your intuition also.

See the first for loop. We know that we are calling the function by function(n/2). Reducing the function exponentially. That is it will run for a time complexity of O(log n).

The second loop will obviously run for n*n.

So the total time complexity will be O(n² log n) . 

Well if you don't get it, go ahead with the conventional way. I just told with respect of exam point of view. 

Answer 3

Since first for loop run 4logn(4T(n/2)) times and second for loop run n^2 times.

Recurrence equation:

T(n)=4T(n/2)+n^2

solving this we get

T(n)=O(n^2 logn )(master theorem case 2)