Data Structure Questions and Answers-Power of a Number using Recursion in Logn Time

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Data Structure Questions and Answers-Power of a Number using Recursion in Logn Time

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What will be the output for following code?

#include<stdio.h>  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
Question 1 Explanation: 
The given program calculates the value of x raised to power y. Thus 23 = 8.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What will be the time complexity of the following code which raises an integer x to the power y?

#include<stdio.h>  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(n2)
Question 2 Explanation: 
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).

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What is the space complexity of the given code?

#include<stdio.h>  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)
Question 3 Explanation: 
The space complexity of the given code will be equal to O(1) as it uses only constant space in the memory.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 4 Explanation: 
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.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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)
Question 5 Explanation: 
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.

There are 5 questions to complete.