Question

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

The question was posed to me in an interview for job.

My question is from Miscellaneous in division Miscellaneous of Data Structures & Algorithms II

Answer 1

The correct answer is (a) to reduce the time complexity of a code

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