## 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?

to reduce the time complexity of a code | |

to increase the space complexity of a code | |

to reduce the space complexity of a code | |

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?

n | |

√n | |

n ^{2} | |

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?

O(n) | |

O(l+r) | |

O(l-r) | |

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?

O(n) | |

O(l+r) | |

O(√n) | |

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?

√n | |

2*√n | |

3*√n | |

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.