Square Root Decomposition

Let us begin with this:

• What is sqrt? sqrt(x) = y         =>           y*y = x

• sqrt(x) is a number y such that y when mulitplied by itself results in x

• to be more accurate in mathematical terms sqrt(y*y) = abs(y) i.e., sqrt of a number is always positive

•  What is decomposition?

• To decompose, to become smaller and simpler, easier - yes its the same thing here

• We have a bigger problem of size n, we decompose it in m smaller problems of size k each.

• n = m*k holds true

• In certain problems upon decomposition in such a fashion, we get Time Complexity such that it is best when the size of smaller problem is sqrt(n) and total number of problems are also sqrt(n). The expression for time complexity minimizes at such a condition

• This decomposition technique in such a scenario where size of each problem is same as total number of smaller problems and is equal to sqrt(n) is called as sqrt decomposition.