This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Square Root Decomposition”.
1. What is the purpose of using square root decomposition?
a) to reduce the time complexity of a code
b) to increase the space complexity of a code
c) to reduce the space complexity of a code
d) to reduce the space and time complexity of a code
View Answer
Explanation: Square decomposition is mainly used in competitive programming to optimize code. It reduces the time complexity by a factor of √n.
2. By what factor time complexity is reduced when we apply square root decomposition to a code?
a) n
b) √n
c) n2
d) n-1/2
View Answer
Explanation: In square root decomposition a given array is decomposed into small parts each of size √n. This reduces the time complexity of the code by a factor of √n.
3. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n?
a) O(n)
b) O(l+r)
c) O(l-r)
d) O(r-l)
View Answer
Explanation: For a given array of size n we have to traverse all n elements in the worst case. In such a case l=0, r=n-1 so the time complexity will be O(n).
4. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) O(n)
b) O(l+r)
c) O(√n)
d) O(r-l)
View Answer
Explanation: When we use square root optimization we decompose the given array into √n chunks each of size √n. So after calculating the sum of each chunk individually, we require to iterate only 3*√n times to calculate the sum in the worst case.
5. Total how many iterations are required to find the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) √n
b) 2*√n
c) 3*√n
d) n*√n
View Answer
Explanation: After calculating the sum of each chunk individually we require to iterate only 3*√n times to calculate the sum in the worst case. It is because two of the √n factors consider the worst case time complexity of summing elements in the first and last block. Whereas the third √n considers the factor of summing the √n chunks.
6. What will be the time complexity of update query operation in an array of size n when we use square root optimization?
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)
View Answer
Explanation: The time complexity of query operation remains the same in both square root optimized code and non optimized code. We simply find the chunk in which the update requires to be performed and then add the new updated value at the desired index.
7. Square root decomposition technique is only applicable when the number of indices in an array is a perfect square.
a) true
b) false
View Answer
Explanation: Square root decomposition technique can be applied to an array with any number of indices. It does not require this number to be a perfect square.
8. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries?
a) O(n)
b) O(q)
c) O(n*q)
d) O(n+q)
View Answer
Explanation: For finding the result of one query the worst case time complexity will be n. So for q queries the time complexity will be O(q*n). This can be reduced by using square root optimization.
9. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries when we apply MO’s algorithm?
a) O(n*q)
b) O(n)
c) O((q+n)√n)
d) O(q*√n)
View Answer
Explanation: Mo’s algorithm requires O(q*√n) + O(n*√n) time for processing all the queries. It is better than the naive solution where O(n*q) time is required.
10. Mo’s algorithm can only be used for problems where the query can be calculated from the result of the previous query.
a) true
b) false
View Answer
Explanation: Mo’s algorithm uses the result of the previous query in order to compute the result of the given query. It cannot be implemented where such a scenario is not possible.
11. What will be the time complexity of the code to find a minimum element from an array of size n and uses square root decomposition(exclude pre processing time)?
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)
View Answer
Explanation: For finding the minimum element in a given array of size n using square root decomposition we first divide the array into √n chunks and calculate the result for them individually. So for a given query, the result of middle blocks has to be calculated along with the extreme elements. This takes O(√n) time in the worst case.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Check Design and Analysis of Algorithms Books
- Practice Programming MCQs
- Check Computer Science Books
- Practice Data Structure MCQ
