250+ TOP MCQs on Power of a Number using Recursion in Logn Time and Answers

Data Structures & Algorithms Multiple Choice Questions on “Power of a Number using Recursion in Logn Time”.

1. What will be the output for following code?

#include 
int func(int x,  int y) 
{ 
	if (y == 0) 
		return 1; 
	else if (y%2 == 0) 
		return func(x, y/2)*func(x, y/2); 
	else
		return x*func(x, y/2)*func(x, y/2); 
} 
int main() 
{ 
	int x = 2; 
    int y = 3; 
 
	printf("%d", func(x, y)); 
	return 0; 
}

a) 9
b) 6
c) 8
d) 5

Answer: c
Clarification: The given program calculates the value of x raised to power y. Thus 2³ = 8.

2. What will be the time complexity of the following code which raises an integer x to the power y?

#include 
int power(int x,  int y) 
{ 
	if (y == 0) 
		return 1; 
	else if (y%2 == 0) 
		return power(x, y/2)*power(x, y/2); 
	else
		return x*power(x, y/2)*power(x, y/2); 
} 
int main() 
{ 
	int x = 2; 
    int y = 3; 
 
	printf("%d", power(x, y)); 
	return 0; 
}

a) O(n)
b) O(log n)
c) O(n log n)
d) O(n²)

Answer: a
Clarification: The recurrence relation for the above code is given by T(n)=2T(n/2)+c. By using master theorem we can calculate the result for this relation. It is found to be equal to O(n).

3. What is the space complexity of the given code?

#include 
int power(int x,  int y) 
{ 
	if (y == 0) 
		return 1; 
	else if (y%2 == 0) 
		return power(x, y/2)*power(x, y/2); 
	else
		return x*power(x, y/2)*power(x, y/2); 
} 
int main() 
{ 
	int x = 2; 
    int y = 3; 
 
	printf("%d", power(x, y)); 
	return 0; 
}

a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: a
Clarification: The space complexity of the given code will be equal to O(1) as it uses only constant space in the memory.

4. Recursive program to raise an integer x to power y uses which of the following algorithm?
a) Dynamic programming
b) Backtracking
c) Divide and conquer
d) Greedy algorithm
Answer: c
Clarification: The recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.

5. What is the least time in which we can raise a number x to power y?
a) O(x)
b) O(y)
c) O(log x)
d) O(log y)
Answer: d
Clarification: We can optimize the code for finding power of a number by calculating x raised to power y/2 only once and using it depending on whether y is even or odd.

6. What will be the time complexity of the following code?

#include 
int power(int x, int y) 
{ 
    int temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2); 
    if (y%2 == 0) 
        return temp*temp; 
    else
        return x*temp*temp; 
} 
int main() 
{ 
	int x = 2; 
    int y = 3; 
 
	printf("%d", power(x, y)); 
	return 0; 
}

a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: c
Clarification: The given code is the optimized version for finding the power of a number. It forms a recurrence relation given by T(n)=T(n/2)+c which can be solved using master theorem. It is calculated to be equal to O(log n).

7. What is the advantage of iterative code for finding power of number over recursive code?
a) Iterative code requires less time
b) Iterative code requires less space
c) Iterative code is more compiler friendly
d) It has no advantage

Answer: b
Clarification: Both iterative and recursive approach can be implemented in log n time but the recursive code requires memory in call stack which makes it less preferable.

8. Which of the following correctly implements iterative code for finding power of a number?
a)

#include  
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
 
        if (y & 1) 
            res = res * x;         
        y = y >> 1; 
        x = x * x;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;   
    printf("%d", power(x, y));   
    return 0; 
}

b)

#include  
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
 
        if (y && 1) 
            res = res * x;         
        y = y >> 1; 
        x = x * x;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;   
    printf("%d", power(x, y));   
    return 0; 
}

c)

#include  
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
        if (y && 1) 
        res = x * x;         
        y = y >> 1; 
        x = x * y;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;   
    printf("%d", power(x, y));   
    return 0; 
}

d)

#include  
int power(int x,  int y) 
{ 
    int res = 1;   
    while (y > 0) 
    { 
        if (y & 1) 
        res = x * x;         
        y = y >> 1; 
        x = x * y;  
    } 
    return res; 
} 
int main() 
{ 
    int x = 3; 
    unsigned int y = 5;  
    printf("%d", power(x, y));   
    return 0; 
}

View Answer

Answer: a
Clarification: It represents the iterative version of required code. It has a time and space complexity of O(log n) and O(1) respectively.

9. Recursive approach to find power of a number is preferred over iterative approach.
a) True
b) False

Answer: b
Clarification: The recursive code requires memory in call stack which makes it less preferable as compared to iterative approach.

10. What will be the output for following code?

float power(float x, int y) 
{ 
	float temp; 
	if( y==0) 
	return 1; 
	temp = power(x, y/2);	 
	if (y%2 == 0) 
		return temp*temp; 
	else
	{ 
		if(y > 0) 
			return x*temp*temp; 
		else
			return (temp*temp)/x; 
	} 
} 
int main() 
{ 
	float x = 2; 
	int y = -3; 
	printf("%f", power(x, y)); 
	return 0; 
}

a) Error
b) 1/4
c) 4
d) 0.25
Answer: d
Clarification: The given code is capable of handling negative powers too. Thus, the output will be 2^-2 = 0.25.

& Algorithms.

and Answers.