Question

Justify the correctness of the recursive division algorithm given in page $\mathbf{25}$, and show that it takes time $\mathbf{O}\mathbf{\left(}{\mathbf{n}}^{\mathbf{2}}\mathbf{\right)}\mathbf{onn}\mathbf{-}$ bit inputs.

Short answer

Recursive division algorithm can be defined as dividing a number from another number which needs to satisfy the condition as,$\mathrm{Dividend}=\mathrm{Divisor}*\mathrm{quotient}+\mathrm{Remainder}$.

Step-by-step solution

Introduction

A recursive function is a piece of code that executes by referencing itself. Simple or complex recursive functions are both possible. They enable more effective code authoring, such as the listing or compilation of collections of integers, strings, or other variables using a single repeated procedure.

Recursive Function

Let the function is given as, $\mathrm{recursive}\_\mathrm{division}$$(\mathrm{a},\mathrm{b})$.

Enter two $\mathrm{n}$-bit integers$\mathrm{a}\mathrm{and}\mathrm{b}$ , where $\mathrm{b}\ge 1$.

Final output is quotient and remainder of a $recursive\_division$ by $b$.

If $\mathrm{a}=0:\mathrm{return}(\mathrm{q},\mathrm{r})=(0,0)$

role="math" localid="1658389148708" $\begin{array}{l}(\mathrm{q},\mathrm{r})=\mathrm{recursive}\_\mathrm{division}(\mathrm{ba}÷2\mathrm{c},\mathrm{b})\\ \mathrm{q}=2\times \mathrm{q},\mathrm{r}=2\times \mathrm{r}\end{array}$

If $\mathrm{x}$ is odd $:r=r+1$

If $\mathrm{r}\ge \mathrm{y}$

$\begin{array}{l}\mathrm{r}=\mathrm{r}-\mathrm{y},\\ \mathrm{q}=\mathrm{q}+1\\ \mathrm{return}(\mathrm{q},\mathrm{r})\end{array}$

Final answer

So, the recursive function will get call up to $2$ times in the given function $\mathrm{n}$. So, time complexity of the given function is $\mathrm{O}\left({\mathrm{n}}^2\right)\mathrm{for}\mathrm{n}$ bits input.