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);

-Write a recurrence that models the running time of this function. Assume checks, returns, and arithmetic are constant time, but be sure to evaluate all function calls. [Hint: what is the most n could be at each level of the recurrence?]

For this I got a base case of T(0)=1 and T(n)=T(n/2)+c.

-Solve the above recurrence for the running time of this function

Explanation / Answer

O(n logn)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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