Why is the running cost of SQUARE-MATRIX-MULTIPLY-RECURSIVE in CLRS $\Theta(n^3)$ instead of $\Theta(n^2)$?

I am reading Introduction to Algorithm CLRS (3rd ed.), Chapter 4 (Divide and Conquer), page 78, and am not sure why the explanation of why SQUARE-MATRIX-RECURSIVE algorithm takes $$Θ(n^3)$$.

Combining equations (4.15) and (4.16) gives us the recurrence for the running time of SQUARE-MATRIX-MULTIPLY-RECURSIVE: $$T(n) = \begin{cases} Θ(1) &\text{if } n=1 \\ 8T(n/2) + Θ(n^2) &\text{if } n>1 \end{cases}$$ As we shall see from the master method in Section 4.5, recurrence (4.17) has the solution $$T(n) = Θ(n^3)$$.

The part that I don't understand is that why $$8T(n/2) + Θ(n^2)$$ becomes $$Θ(n^3)$$. I only see $$n^2$$ in the term but why would it become $$n^3$$?

• I don't really understand your question. Did you look at Section 4.5? It should explain exactly why $T(n)=\Theta(n^3)$. Did you not understand the explanation there? If so, what part? Do you not understand why $T(n)$ is the right expression for the complexity? Something else? – David Richerby Feb 8 at 22:14
• Thanks @DavidRicherby, I edited. – eeee Feb 8 at 22:22
• @eeee "As we shall see from the master method in Section 4.5, recurrence (4.17) has the solution $T(n) = Θ(n^3)$." The CLRS wants you to understand a while later down the road when you will read Section 4.5. There is little point for people to answer here if you have not read that section. – Apass.Jack Feb 8 at 23:18
• @eeee OK, thanks. But you've missed the most important part. Did you look at Section 4.5? The text you quote explictly says that Section 4.5 will answer your question. If you didn't look at that, why are you asking us to tell you this stuff instead of just looking a few pages ahead in the book you're already reading? – David Richerby Feb 9 at 10:47

2 Answers

What you are asking is indeed answered in section 4.5 of CLRS using a methodology described later in the book. I will post here an alternative answer you should be able to understand with your current knowledge.

Think of the recursive relationship $$T(n) = 8T(\dfrac{n}{2}) + cn^2.$$

Let us first see what happens if we substitute $$T(\dfrac{n}{2})$$

$$T(n) = 8 (8T(\dfrac{n}{4}) + c (\dfrac{n}{2})^2) + cn^2 = 8^2 T(\dfrac{n}{4}) + 8c(\dfrac{n}{2})^2 + cn^2.$$

By substituting $$T(\dfrac{n}{4})$$ we get:

$$T(n) = 8^2 (8T(\dfrac{n}{8}) + c (\dfrac{n}{4})^2) + 8c(\dfrac{n}{2})^2 + cn^2 = 8^3 T(\dfrac{n}{8}) + 4cn^2 + 2cn^2 + cn^2.$$

It becomes obvious that in the general case after $$k$$ iterations we have:

$$T(n) = 8^k T(\dfrac{n}{2^k}) + cn^2(2^{k-1} + 2^{k-2} + \dots + 2 + 1).$$

Let $$n = 2^k$$.

Notice that $$k = \log_2n \Rightarrow8^k = 8^{\log_2n} = 2^{3\log_2n} = 2^{\log_2n^3} = n^3$$. By substituting $$k = \log_2n$$ in the previous relationship we get:

$$T(n) = n^3T(1) + cn^2 (\dfrac{1}{2} + \dfrac{1}{4} + \dots + \dfrac{1}{n})n.$$

$$T(n) = n^3 T(1) + cn^3$$, therefore you have $$\Theta (n^3)$$.

Here is a simpler example that could be useful. Consider the recurrence

$$T(n) = \begin{cases} 1 & \text{if }n = 1, \\ T(n-1)+1 & \text{if } n > 1. \end{cases}$$

The solution to this recurrence is $$T(n) = n$$, although the additive term in the recurrence is only $$1$$.