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
- Theta(log n)
- Theta(n log n)
- Theta(n^2)
- Theta(n)