# Generating Permutations Multiple choice Questions and Answers (MCQs)

## Click on any option to know the CORRECT ANSWERS

 Question 6
What is the time complexity of Heap's algorithm?
 A O(n log n) B O(n2) C O(n*n!) D O(n!)

Question 6 Explanation:
The recurrence relation for the heap's algorithm is given by the expression T(n)=n * T(n-1). It is calculated by using substitution method. It is found to be equal to O(n!).

 Question 7
What will be the output for following code?

#include <stdio.h>  #include <string.h>  #include<iostream> using namespace std; void swap(char *x,  char *y) { 	char temp; 	temp = *x; 	*x = *y; 	*y = temp; } void func(char *a,  int l,  int r) { int i; if (l == r) 	cout<<a<<" , "; else { 	for (i = l; i <= r; i++) 	{ 		swap((a+l),  (a+i)); 		func(a,  l+1,  r); 		swap((a+l),  (a+i)); 	} } } int main() { 	char str[] = "AB"; 	int n = strlen(str); 	func(str,  0,  n-1); 	return 0; }
 A AB, BA, B BA, AB, C AB, BA D BA, AB,

Question 7 Explanation:
The given code prints the permutations of the an array. So there will be 2 permutations for an array of 2 elements. Note that the comma is printed even for the last permutation.

 Question 8
What will be the time complexity of the given code?

#include <stdio.h>  #include <string.h>  #include<iostream> using namespace std; void swap(char *x,  char *y) { 	char temp; 	temp = *x; 	*x = *y; 	*y = temp; } void func(char *a,  int l,  int r) { int i; if (l == r) 	cout<<a<<" , "; else { 	for (i = l; i <= r; i++) 	{ 		swap((a+l),  (a+i)); 		func(a,  l+1,  r); 		swap((a+l),  (a+i)); 	} } } int main() { 	char str[] = "AB"; 	int n = strlen(str); 	func(str,  0,  n-1); 	return 0; }
 A O(n2) B O(n * n!) C O(n!) D O(n log n)

Question 8 Explanation:
The recurrence relation for the heap's algorithm is given by the expression T(n)=n * T(n-1). But as each permutations takes n time to be printed so the overall complexity will be O(n*n!).

 Question 9
What will be the output of the following code?

#include <iostream> #include<string> using namespace std; void func1(string input, string output) { if(input.length()==0) { cout<<output<<", "; return; } for(int i=0;i<=output.length();i++) func1(input.substr(1), output.substr(0, i) + input + output.substr(i)); } int main() { char str[] = "AB"; 	func1(str,  ""); return 0; }
 A AA, BA, B AB, BA, C BA, AB, D AB, AB,

Question 9 Explanation:
The given code prints the permutations of the an array. So there will be 2 permutations for an array of 2 elements. In this code the difference is that BA is printed before AB. Note that the comma is printed even for the last permutation.

 Question 10
What will be the output of the following code?

#include <stdio.h>  #include <string.h>  #include<iostream> using namespace std; void swap(char *x,  char *y) { 	char temp; 	temp = *x; 	*x = *y; 	*y = temp; } void func(char *a,  int l,  int r) { int i; if (l == r) 	cout<<a<<" , "; else { 	for (i = l; i <= r; i++) 	{ 		swap((a+l),  (a+i)); 		func(a,  l+1,  r); 		swap((a+l),  (a+i)); 	} } } int main() { 	char str[] = "AA"; 	int n = strlen(str); 	func(str,  0,  n-1); 	return 0; }
 A AA, B AA, AA C A, A D AA, AA,