# Karatsube-Ofman runtime complexity computation

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

• This is just the proof of the master theorem in a special case. Look up any proof of the master theorem for an explanation of all the steps. Nov 8, 2021 at 11:07
• thanks! I didn't find it when search for "Karatsube-Ofma proof", so does mean it works for all recurrence relations ? or just specific equations ? Nov 8, 2021 at 11:19
• The master theorem applies to all recurrence relations to which it applies. It does not apply to recurrence relations to which it does not apply. Nov 8, 2021 at 11:20
• hmm I can't select best answer from comment should I delete my question ? Nov 8, 2021 at 11:24
• I'll write an answer. Nov 8, 2021 at 11:25