I-Gate Question

Question

Consider the following algorithm,

Dosomething( x, n)

{

m= n, temp= 1,z= x;

while(m>0) do

{

while((m mod z)=0) do

{

m= Floor(m/2);

z=z^2;

}

m = m-1, temp= temp* z;

}

return temp;

}

The complexity of above algorithm is

• A. Theta(log n)
• B. Theta(n log n)
• C. Theta(n^2)
• D. Theta(n)

Comments

I think it will be either A or D.

I am getting O(n) as worst case and best case as log(n).

---

@loki2023What answer is given?

---

The outer while loop cannot run exactly ‘n’ times because the inner while loop is updating the value of m by using m = floor(m/2);

Most probably, option A will be the answer.