# Complexity of divide and conquer algorithm with a quadratic merge function

Consider the following pseudocode:

int divide(int l , int r){
if r - l > 3 then
mid = (l + r) / 2
divide(l , mid)
divide(mid + 1, r)
return merge(l, mid, r)
else
return bruteforce_solution(l, r)
}


If merge function takes $O(n^2)$ time, then total complexity can be found as a solution of the reccurence: $T(n)=2T(n/2)+n^2$
The solution of a the reccurence is $T(n)=2n^2-n$
So $O(log(n))$ calls of an $O(n^2)$ function takes $O(n^2)$ time?

Let $S(n) = T(n)/n^2$. Then $$S(n) = \frac{T(n)}{n^2} = \frac{2T(n/2)}{n^2} + 1 = \frac{2(n/2)^2S(n/2)}{n^2} + 1 = \frac{S(n/2)}{2} + 1.$$ Assuming a base case of $S(1) = 2$ and that $n$ is a power of $2$, one can prove by induction that $S(n) = 2$. Indeed, this holds for $n = 1$, and if it holds for $n/2$, then $$S(n) = S(n/2)/2 + 1 = 2/2 + 1 = 2.$$ We conclude that if $T(1) = 2$ and $n$ is a power of $2$ then $T(n) = 2n^2$.
What happened here? First we had one call to a routine that takes time $n^2$. Then we had two calls to a routine that takes time $(n/2)^2 = n^2/4$, taking a total time of $n^2/2$. Then we had four calls to a routine that takes time $(n/4)^2 = n^2/16$, taking a total time of $n^2/4$. And so on. The amount of work at each level decreases exponentially, and so the total amount of work stays $O(n^2)$ although there are $\log n$ different levels.
If we replaced $2T(n/2)$ by $aT(n/b)$, then the behavior of the recurrence would depend on the relation between $\log_b a$ and $2$. This is covered by the well-known master theorem.