in Algorithms retagged by
142 views
2 votes
2 votes

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

  1. Theta(log n)
  2. Theta(n log n)
  3. Theta(n^2)
  4. Theta(n)
in Algorithms retagged by
142 views

3 Comments

I think it will be either A or D.

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

@loki2023What answer is given?

1
1
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.
0
0

Please log in or register to answer this question.

Related questions