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