Consider the pseudocode function below. derp( x, n ) if ( n == 0 ) return 1; if(

Question

Consider the pseudocode function below. derp( x, n ) if ( n == 0 ) return 1; if( n % 2 == 0 ) return derp( x^2, n/2 ); return x * derp( x^2, (n - 1) / 2); What is the output when passed the following parameters: x = 2, n = 12. Show your work (activation diagram or similar). Briefly describe what this function is doing. Write a recurrence that models the running time of this function. Assume checks, returns, and arithmetic arc constant time, but be sure to evaluate all function calls. (Hint: what is the most n could be at each level of the recurrence? Solve the above recurrence for the running time of this function.

Explanation / Answer

once the control entered the function derp it checks if n==0 or n%2==0 as the parameters are x=2 and n=12 12 !=0 and 12%2=0 so as n%2 is true it returns arguments 2^2 ,12/2 i.e; 4,6 again it checks if n==0 or n%2==0 6%2=0 so it returns arguments 16,3 in this case 3!=0 and 3%2!=0 then it returns 16*derp(16,2.5) then 16*derp(16,2.5) loop continues

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.