int special(const int* array, int p, int r) {
if (p == r) {
return 0;
}
int sum = 0;
for (int i = p; i < r; i += 1) {
sum += array[i];
}
int q = (p + r) / 2;
return sum + special(array, p, q) + special(array, q + 1, r);
}
I want to know this code's time and space complexity.
I think that Time Complex is Tn = 1 + Tn/2 + Tn/2, so the answer is Tn = 2n -1 ,But The answer is O(nlogn)
Who is know the solution?
Your recurrence for Tn was just a bit off.
It is true that you recurse on two size subproblems. However, the work you do in every function call besides recursing is not O(1): you iterate over the portion of the array from p to r. Because each function call only does work proportional to r-p, we should take input size n = r-p. Or equivalently, we could think of each recursive call as receiving the size n subarray bounded by indices [p, r). In either case, the work in each function call, represented by the for loop from p to r, is O(n), not O(1). So the recurrence is:
T(n) = 2T(n/2) + n
This is the same recurrence which expresses the complexity of standard sorting algorithms like mergeSort or quickSort, which could already clue you in to why the overall time is O(nlogn).
One way to see how this recurrence leads to nlogn complexity is to think in terms of a recursion tree.
At the top level, there is 1 function call which does O(n) work.
At the second level, there are 2 function calls, each doing O(n/2) work. Total work = 2*O(n/2) = O(n)
At the third level, there are 4 function calls, each doing O(n/4) work. Total work = 4 * O(n/4) = O(n) ... and so on
O(n) work is done at every level of the tree, until the base case is reached and recursion stops. Because sub-problem size is divided in two at every iteration until it reaches 0 and stops recursing, there are about log(n) levels until the recursion stops, bringing the overall complexity to O(n)*log(n) = O(nlogn)
The space complexity, however, is only log(n), as each function call only uses O(1) space (because you pass a pointer and two indices, not a copy of the array). As the call-stack can get log(n) recursive calls deep, total space = O(1)*log(n) = O(logn)