c - 递归函数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;
    }
}

假设除法运算需要常数时间，sum 是一个全局变量。 find(n) 的时间复杂度是多少？

根据我的说法:因为第一个 for 循环运行 4 log n 次，第二个 for 循环运行 n^2 次。所以总时间复杂度 = 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))

主定理的案例 2。 https://en.wikipedia.org/wiki/Master_theorem