Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Square Root Decomposition”.
1. What is the purpose of using square root decomposition? Answer: a 2. By what factor time complexity is reduced when we apply square root decomposition to a code? Answer: b 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? Answer: a 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? Answer: c 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? 6. What will be the time complexity of update query operation in an array of size n when we use square root optimization? 7. Square root decomposition technique is only applicable when the number of indices in an array is a perfect square. Answer: b 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? Answer: c 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? 10. Mo’s algorithm can only be used for problems where the query can be calculated from the result of the previous query. 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)? Answer: a
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
Clarification: Square decomposition is mainly used in competitive programming to optimize code. It reduces the time complexity by a factor of √n.
a) n
b) √n
c) n2
d) n-1/2
Clarification: 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.
a) O(n)
b) O(l+r)
c) O(l-r)
d) O(r-l)
View Answer
Clarification: 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).
a) O(n)
b) O(l+r)
c) O(√n)
d) O(r-l)
Clarification: 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.
a) √n
b) 2*√n
c) 3*√n
d) n*√n
Answer: c
Clarification: 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.
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)
Answer:c
Clarification: 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.
a) true
b) false
Clarification: 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.
a) O(n)
b) O(q)
c) O(n*q)
d) O(n+q)
Clarification: 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.
a) O(n*q)
b) O(n)
c) O((q+n)√n)
d) O(q*√n)
Answer: c
Clarification: 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.
a) true
b) false
Answer: a
Clarification: 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.
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)
Clarification: 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.