1
$\begingroup$

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:

enter image description here

with some estimates and the partial summation of the geometrical series follows:

enter image description here

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Nov 8, 2021 at 11:07
  • $\begingroup$ 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 ? $\endgroup$
    – MR.-c
    Nov 8, 2021 at 11:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Nov 8, 2021 at 11:20
  • $\begingroup$ hmm I can't select best answer from comment should I delete my question ? $\endgroup$
    – MR.-c
    Nov 8, 2021 at 11:24
  • $\begingroup$ I'll write an answer. $\endgroup$
    – Yuval Filmus
    Nov 8, 2021 at 11:25

1 Answer 1

Reset to default
2
$\begingroup$

The recurrence relation you give can be handled by the master theorem. Any proof of the master theorem will include similar steps (in more generality). A good proof of the master theorem should carefully explain all the steps in the proof.

Beware, though, that the master theorem includes three different cases, and you're interested in only one of them (case 1 in the numbering used by Wikipedia).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.