1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.