We are given a sequence $M(n)$ and we know that $M(n) = O\left(n^2\right)$. Why does it follow that $M\left(\frac{n}{2}\right) + M\left(\frac{n}{4}\right) + \ldots + M\big(1\big) = O\big(M(n)\big)\,$?
I need this to solve problem 0.4 in Dasgupta's book Algorithms. I couldn't figure it out myself and the internet was of no help either - I found two solutions but I couldn't understand either of them.
$M(n/2) + M(n/4)+ \cdots + M(1) = O(n^2/4)+O(n^2/16)+O(n^2/64)+ \cdots $.
Because all the $O$ have the same constant (they come from the same estimate of the function $M$), you can factor them out like this (go back to the definition $\leq Cn^2$ if you want to see why).
$\cdots = O(n^2) (1/4 + 1/16 + 1/64 + \cdots) = O(n^2)$ because the factor is a convergent series.
I don't think you can get anything better, in particular $O(M(n))$, unless you assume stronger regularity estimates on $M$.