Count Inversion Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Count Inversion”.

1. What does the number of inversions in an array indicate?
a) mean value of the elements of array
b) measure of how close or far the array is from being sorted
c) the distribution of values in the array
d) median value of the elements of array
View Answer

Answer: b
Explanation: The number of inversions in an array indicates how close or far the array is from being completely sorted. The array is sorted if the number of inversions are 0.

2. How many inversions does a sorted array have?
a) 0
b) 1
c) 2
d) cannot be determined
View Answer

Answer: a
Explanation: When an array is sorted then there cannot be any inversion in the array. As the necessary condition for an inversion is arr[i]>arr[j] and i<j.

3. What is the condition for two elements arr[i] and arr[j] to form an inversion?
a) arr[i]<arr[j]
b) i < j
c) arr[i] < arr[j] and i < j
d) arr[i] > arr[j] and i < j
View Answer

Answer: d
Explanation: For two elements to form an inversion the necessary condition is arr[i] > arr[j] and i < j. The number of inversions in an array indicate how close or far the array is from being completely sorted.
advertisement
advertisement

4. Under what condition the number of inversions in an array are maximum?
a) when the array is sorted
b) when the array is reverse sorted
c) when the array is half sorted
d) depends on the given array
View Answer

Answer: b
Explanation: Number of inversions in an array are maximum when the given array is reverse sorted. As the necessary condition for an inversion is arr[i]>arr[j] and i<j.

5. Under what condition the number of inversions in an array are minimum?
a) when the array is sorted
b) when the array is reverse sorted
c) when the array is half sorted
d) depends on the given array
View Answer

Answer: a
Explanation: Number of inversions in an array are minimum when the given array is sorted. As the necessary condition for an inversion is arr[i]>arr[j] and i<j.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. How many inversions are there in the array arr = {1,5,4,2,3}?
a) 0
b) 3
c) 4
d) 5
View Answer

Answer: d
Explanation: The necessary condition for an inversion is arr[i]>arr[j] and i<j. So there are 5 inversions in the array.

7. Which of the following form inversion in the array arr = {1,5,4,2}?
a) (5,4), (5,2)
b) (5,4), (5,2), (4,2)
c) (1,5), (1,4), (1,2)
d) (1,5)
View Answer

Answer: b
Explanation: The necessary condition for an inversion is arr[i]>arr[j] and i<j. So there are 3 inversions in the array. These are (5,4), (5,2), (4,2).
advertisement

8. Choose the correct function from the following which determines the number of inversions in an array?
a)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i ; j < n; j++) 
			if (arr[i] >= arr[j]) 
				count++; 
 
	return count; 
}

b)

advertisement
int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count; 
}

c)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count + 1; 
}

d)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] < arr[j]) 
				count++; 
 
	return count + 1; 
}
View Answer
Answer: b
Explanation: To determine the number of inversions we apply a nested loop and compare the value of each element with all the elements present after it. Then the count of number of inversions is counted and returned to the main function.
 
 

9. What is the time complexity of the following code that determines the number of inversions in an array?

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count; 
}

a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: c
Explanation: The time complexity of the given code is O(n2). It is due to the presence of nested loop.

10. The time complexity of the code that determines the number of inversions in an array using merge sort is lesser than that of the code that uses loops for the same purpose.
a) true
b) false
View Answer

Answer: a
Explanation: The time complexity of the code that determines the number of inversions in an array using merge sort is O(n log n) which is lesser than the time complexity taken by the code that uses loops.

11. What is the time complexity of the code that uses merge sort for determining the number of inversions in an array?
a) O(n2)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

Answer: d
Explanation: The code of merge sort is slightly modified in order to calculate the number of inversions in an array. So the time complexity of merge sort remains unaffected and hence the time complexity is O(n log n).

12. What is the time complexity of the code that uses self balancing BST for determining the number of inversions in an array?
a) O(n2)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

Answer: d
Explanation: When a self balancing BST like an AVL tree is used to calculate the number of inversions in an array then the time complexity is O(n log n) as AVL insert takes O(log n) time.

13. The time complexity of the code that determines the number of inversions in an array using self balancing BST is lesser than that of the code that uses loops for the same purpose.
a) true
b) false
View Answer

Answer: a
Explanation: The time complexity of the code that determines the number of inversions in an array using self balancing BST is O(n log n) which is lesser than the time complexity taken by the code that uses loops.

14. What is the space complexity of the code that uses merge sort for determining the number of inversions in an array?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
View Answer

Answer: a
Explanation: The space complexity required by the code will be O(n). It is the same as the space complexity of the code of standard merge sort.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.