This kind of questions are a bit confusing as they trick our eyes into believing that the coefficient present in the function call should be the constant in the time complexity recurrence as well.
When you have a recurrence of the sort of:
T(n)=aT(n/b)+c
what this actually means is that every time your function is called, it will in turn call itself 'a' more times in that very instance untill it reaches base case where it begins to die:
To explain this statement with an example, suppose I have the following function:
A(n)
{
//The base condition where the function is finally relieved of its boredom
if(n==1)
return 1;
else
//The mighty recurrence
return(2A(n/2)+3A(n/2));
}
You can clearly see that I am calling the function A() two times once with a coefficient 2 and once with a coefficient 3, Since I am calling it two times, the recurrence for time complexity will be as below:
T(n)=2T(n/2)+O(1)
the question that comes now is what happens to our beloved 2 and 3 present in function calls, well they are nothing more that some numbers waiting to be multiplied. When the first A(n/2) comes back to its calling point we multiply 2 to it and when the second A(n/2) comes back we multiply 3 to it. This multiplication is a simple constant time operation (in current context), and same goes for their addition. Both these operations are covered in our mighty O(1).
Coming back to your question, we can clearly see that each time the function makes only one recurrence call to itself:
X+=8A(n/2)+n^3;
and 8 is simply a constant waiting to be multiplied. As for n3 it is simply calculable in constant time.
therefore the recurrence should be:
T(n)=T(n/2)+O(1)
Nice question, you made me think a lot.
