I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample.
Question: One can generalize the Karatsube-Ofman algorithm even further and divide the number to be squared into b parts with n / b places. However, one then has to perform 2b - 1 recursive squaring of numbers with n / b digits 2 plus O (n) overhead for various “simple” operations. Represent the running time Q b (n) of this method by a recursion equation and try to solve this recursion. Which asymptotic running time is achieved?
Solution: there exists $\alpha$ and $\beta$ such that:
with some estimates and the partial summation of the geometrical series follows:
My questions:
1: how did we convert the $(2b+1)Q_b(\frac{n}{b}+\beta n)$ to the first line of the ?
2: did we use the sum since it's for all number $n\geq 2$?
3: in first line why did we multiply $\beta$ with $(2b-1)$?
4: why $\log_b(n)-1$ above the sum ?
5: in third line how did we remove the sum?
6: in fourth line why did we use inequality ?
7: in fifth line how did it get converted ? from 3 and 4