Allen Career Institute:Programming

Question

Do something (x, n)
{
m = n, temp = 1, z = x ;
   while (m > 0) do
{
while ((m mod z) == 0) do
{
   m = |m/2|;
   z = z^{2} ;
}
m = m – 1;
}
return temp ;
}

Complexity of the above problem

$1)\Theta \left ( log n \right )$

$2)\Theta \left ( nlog n \right )$

$3)\Theta \left (n^{2} \right )$

$4)\Theta \left (n\right )$

 

Comments

@ankitgupta.1729

I think ur point is valid

there may be any point when m mod z can never be 0

---

@ankitgupta.1729 is right. I just couldn't see the case. For some reason, I kept thinking that the statement inside while loop is

m%z !=0.

 

​​​​​​@srestha you asked the question right? Is there a way to know what temp xz is? What if it's temp = something(x,z)?

---

I removed that line

ok now?