Does the multiplication of the recursive calls affect the master's theorem?

56 Views Asked by At

I have the following code snippet that I need to calculate its complexity.

int T2 (int n) {
    int c = 0;
    if (n < 2) 
        return 1; 
    else
        for (int i = 1; i < n; i = i + 1)
            c++;
    return c + 4 * T2 (n / 9) * T2 (n / 9) + T2 (n / 9);
}

As this is a recursive function where we are dividing n by 9 in each call, I believe that master's theorem apply here. If we consider that "a" is equal to the number of subproblems, can I simply consider a=3 when applying master's theorem or does the multiplication of calls change that? That is, can I say that T(n) = 3T(n/9) + O(n)? where O(n) came from the for loop in the algorithm:

for (int i = 1; i < n; i = i + 1)
    c++;
0

There are 0 best solutions below