Question

A positive integer $\mathbf{N}$ is a power if it is of the form${\mathbf{q}}^{\mathbf{k}}$ , where ${\mathbf{q}}^{}$,role="math" localid="1658399000008" $\mathbf{k}$ are positive integers and $\mathbf{k}\mathbf{>}\mathbf{1}$.

(a) Give an efficient algorithm that takes as input a number and determines whether it is a square, that is, whether it can be written as${\mathbf{q}}^{\mathbf{2}}$ for some positive integer ${\mathbf{q}}^{}$. What is the running time of your algorithm?

(b) Show that if $\mathbf{N}\mathbf{=}{\mathbf{q}}^{\mathbf{k}}$ (with role="math" localid="1658399171717" $\mathbf{N}$,$\mathbf{q}$ , and$\mathbf{k}$ all positive integers), then either role="math" localid="1658399158890" $\mathbf{}\mathbf{k}\mathbf{\le }\mathbf{logN}\mathbf{}\mathbf{or}\mathbf{}\mathbf{N}\mathbf{=}\mathbf{1}$.

(c) Give an efficient algorithm for determining whether a positive integer$\mathbf{N}$ is a power. Analyze its running time.

Short answer

1. It is having$\mathrm{O}\left(\log 2^{\mathrm{n}}\right)$ iterations and the total running time of the algorithm is $\mathrm{O}\left({\mathrm{n}}^3\right)$.
2. $\mathrm{If}\mathrm{q}=1$then, the value of $\mathrm{N}$must equal to$1$ .
3. The running time complexity of the given algorithm is $\mathrm{O}\left({\mathrm{n}}^6\right)$.

Step-by-step solution

Introduction

The running time complexity can be defined as the total amount of time taken to complete the process. It generally analyzes the time taken at each step and finally it computes for the final time complexity.

(a) Algorithm to find whether the input number N is a square or not

Let’s consider that$\mathrm{N}$ is having $\mathrm{n}$bits.

So, we are performing a binary search on the given ‘ $\mathrm{n}$’ interval $[2\mathrm{n}-1,1]$.

It helps me to analyze that it is having a number that is${\mathrm{q}}^2=\mathrm{N}$ .

For each iteration,

It generally takes time$\mathrm{O}\left({\mathrm{n}}^2\right)$ to square of the current element.

It takes$\mathrm{O}\left(\mathrm{n}\right)$ to analyze and compare the result with N.

So, it is having$\mathrm{O}\left(\log 2^{\mathrm{n}}\right)$ iterations and the total running time of the algorithm is $\mathrm{O}\left({\mathrm{n}}^3\right)$.

(b) If N=qk  then prove either  k≤log N or N=1

We have, $\mathrm{N}={\mathrm{q}}^{\mathrm{k}}$.

Taking log both side

$\log \mathrm{N}=\log {\mathrm{q}}^{\mathrm{k}}$

We can write this expression as,

$\begin{array}{c}\mathrm{logN}=\mathrm{k}\log \mathrm{q}\\ \mathrm{k}=\mathrm{logN}/\mathrm{logq}\end{array}$

$\mathrm{k}=\mathrm{logN}/\mathrm{logq}$

$\mathrm{for}\mathrm{all}\mathrm{q}>1,$we have

$\mathrm{k}\le \mathrm{logN}$

$\mathrm{If}\mathrm{q}=1$then, the value of$\mathrm{N}$ must equal to $1$.

(c) Algorithm for determining whether a positive integer N is a power

For the given question, we can use the same algorithm from part (a).

But, instead of squaring the number, we have to raise numbers to power ‘ $\mathrm{k}$’ and we need to check if we get the value of $\mathrm{N}$.

It takes$\mathrm{O}\left(\mathrm{n}\right)$ iterations as from

$\mathrm{for}(\mathrm{i}=1\mathrm{tok}(\mathrm{inn}\left)\right)$

Time taken$\mathrm{O}({\mathrm{k}}^2\times {\mathrm{n}}^2)$

So, this algorithm takes time $\mathrm{O}({\mathrm{k}}^2\times {\mathrm{n}}^3)$.

If the value of the power is$\mathrm{N}$ then, we have to compute for all$\mathrm{k}<=\mathrm{logN}<=\mathrm{n}$ .

Therefore, the running time complexity of the given algorithm is $\mathrm{O}\left({\mathrm{n}}^6\right)$.