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

## Click on any option to know the CORRECT ANSWERS

 Question 1
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
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
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
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