We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I see what your point is, but some hardware do provide primitives for square roots, so just as addition and multiplication can be thought of as a basic operation, so too can floating point square roots. For example, the Pentium Pro can compute 80-bit floating point square roots in 69 cpu cycles - this is fixed and does not vary with input size.
However, if your Math library does floating point square roots in software rather than in hardware, it probably uses the O(log(n)) Newton method. I belive the sqrt in C++'s cmath actually does square root using Newton method, so in that case it is actually O(log(n)).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Squares
You are viewing a single comment's thread. Return to all comments →
I see what your point is, but some hardware do provide primitives for square roots, so just as addition and multiplication can be thought of as a basic operation, so too can floating point square roots. For example, the Pentium Pro can compute 80-bit floating point square roots in 69 cpu cycles - this is fixed and does not vary with input size.
However, if your Math library does floating point square roots in software rather than in hardware, it probably uses the O(log(n)) Newton method. I belive the sqrt in C++'s cmath actually does square root using Newton method, so in that case it is actually O(log(n)).