The time complexity of the recursive function find (n)

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;
    }
}

Suppose that the division operation takes a constant time, and suma global variable. What is time complexity find(n) ?

For me: since the first for loop runs 4 log nonce and the second for the run cycle n^2times. Thus, the total time complexity = O(4 log n + n^2) = O(n^2).

Answer 1

T(n) = 4 * T(n/2) + O(n^2)
a = 4, b = 2, f(n) = n^2
f(n) = O(n^c log^k(n)) , c = 2, k = 0
logb(a) = log2(4) = 2, c = logb(a)
T(n) = Theta(n^(logb(a))log^(k+1)n) = Theta(n^2*log^1(n)) = Theta(n^2*log(n))

Case 2 of the main theorem. https://en.wikipedia.org/wiki/Master_theorem

Answer 2

The first loop issues O (log (n)) times, each time invoking itself. Upon return, each call will cause an O (n ^ 2) loop.

Hence, O(n^2 log(n))

Answer 3

. n^2 + (n/2)^2 + (n/4)^2 + .. O (n ^ 2), 2 * (n ^ 2). .

, O (n).

for (i = 1; i <= 4; i++) find(n / 2); 
for (i = 1; i <= n; i++)
    sum = sum +1;

O (n)