# Square Root Decomposition Multiple choice Questions and Answers (MCQs)

## Click on any option to know the CORRECT ANSWERS

 Question 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

Question 1 Explanation:
Square decomposition is mainly used in competitive programming to optimize code. It reduces the time complexity by a factor of √n.

 Question 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

Question 2 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.

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

Question 3 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).

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

Question 4 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.

 Question 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