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.

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.

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}$

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.