I am reading the Chapter 28 Matrix Operations Section 2 of Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. I particularly need help with understanding Theorem 28.2 (Inversion is no harder than multiplication).
Let I(n) be the complexity of finding an inverse of an $n\times n$ matrix, and $M(n)$ be the complexity of multiplying two $n\times n$ matrices. We assume that $M(n) = \Omega(n^2)$.
The regularity condition is given as : $M(n/2) \leq c M(n)$ for some constant $c <1/2$.
Now the proof includes the following steps:
$$I(n) \leq 2I(n/2) + 4 M(n/2) + O(n^2)$$ $$ = 2I(n/2) + \Theta(M(n))$$ $$ = \mathcal{O}(M(n))$$
Next, the book says that the second line holds because the regularity condition implies that $4M(n/2) <2 M(n)$ and because we assume that $M(n) = \Omega(n^2)$.
Now I understand how $4M(n/2) <2 M(n)$ follows. But I don't understand how $4 M(n/2) + O(n^2) = \Theta(M(n))$ holds.
The book next says that third line follows because the regularity condition allows us to use the masters theorem. I don't understand how the masters theorem leads to the third line $I(n) = \mathcal{O}(M(n))$.
Could you please help understand these details?
Regarding your first question referring to the second line in the proof we compute the time complexity of:
$$ T(n) = 4M \left( \frac{n}{2} \right) + n^2 $$
From the regularity condition $M\left( \frac{n}{2} \right) \leq c M(n)$, $c < 1/2$ we get:
$$ T(n) \leq 4cM(n) + n^2 $$
We have that $M(n) = \Omega (n^2)$. We now assume $T(n) \leq k M(n)$ and get:
$$ T(n) \leq 4 c M(n) + n^2 \leq k M(n) $$
Or:
$$ n^2 \leq \left(k - 4c \right) M(n) $$
Which holds if $k - 4c \geq 1$, i.e.:
$$ k \geq 4c + 1 $$
So we conclude that $T(n) = O(M(n))$ or:
$$ 4M \left( \frac{n}{2} \right) + n^2 = O(M(n)) $$
What we also could have done is note that $c < 1/2$ and if we take $c = 1/2$ we get the asymptotic bound to $T(n)$:
$$ T(n) = 2 M(n) + n^2 = \Theta(M(n)) $$
which holds since $M(n) = \Omega(n^2)$ and is tighter, and is the conclusion arrived at in the book.
Regarding your second question referring to the third line of the proof we can apply the master theorem. The master theorem holds for recurrences of the form:
$$ T(n) = a T \left( \frac{n}{b} \right) + f(n)$$
We have that:
$$ I(n) = 2 I \left( \frac{n}{2} \right) + M(n)$$
We know that $M(n) = \Omega (n^2)$ and taking $f(n) = M(n)$ and $T(n) = I(n)$ the third case of the master theorem holds so $T(n) = \Theta(f(n))$, implying $I(n) = O(M(n))$ since the above is really an inequality.