Square Root Decomposition Multiple choice Questions and Answers (MCQs)

 

 Help authour, Buy PDF Ebook   >>>Click Here<<<

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
UPSC Questions answers

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
Economics Questions answers

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)
Civics Test Questions answers

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)
HRM Questions answers

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
EVS Questions answers

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

There are 5 questions to complete.

 

 Download all FREE PDF Ebook >>>CLICK HERE<<<