Time complexity of Math.Sqrt()?

Question

How can I find the complexity of this function?

private double EuclideanDistance(MFCC.MFCCFrame vec1, MFCC.MFCCFrame vec2)
{
  double Distance = 0.0;
  for (int K = 0; K < 13; K++)
     Distance += (vec1.Features[K] - vec2.Features[K]) * (vec1.Features[K] - vec2.Features[K]);
  return Math.Sqrt(Distance);
}

I know that the below section is O(1):

double Distance = 0.0;
for (int K = 0; K < 13; K++)
   Distance += (vec1.Features[K]-vec2.Features[K])*(vec1.Features[K]-vec2.Features[K]);

But I can't figure out what the complexity of Math.Sqrt() is.

Just wondering, shouldn't that for statement be of a time complexity of O(n) as it effectively iterates over an array? — RedLaser, Jan 03 '16 at 19:09
[sqrtd](https://www.felixcloutier.com/x86/sqrtpd) reference, which what is likely how `Math.Sqrt()` is computed. — JAlex, May 18 '21 at 17:19

score 11 · Answer 1 · answered May 20 '21 at 11:57

11

As mentioned by BlackBear, the Math.Sqrt implementation translates to a to a single floating point machine code instruction (fsqrt). The number of cycles of this instruction is bounded (here are some examples). And that means its complexity is O(1).

That is only true, because we use a limited number of floating-point values. The "actual" complexity of that operation depends on the number of bits of the input. Here you can find a list of the complexity of basic arithmetic functions. According to that list the squareroot function has the complexity of the multiplication function (O(n log n) for two n-digit numbers).

You said, that you assume addition and multiplication function have complexity O(1). That means, you can assume that the squareroot function, allthough much slower, has complexity O(1), too.

answered May 20 '21 at 11:57

winkeldings

314
2
3

There is no algorithm which would compute a square root in constant time. https://cstheory.stackexchange.com/questions/9706/complexity-of-finding-the-square-root-of-a-perfect-square#:~:text=The%20square%20root%20of%20an,)%2C%20provided%20by%20F%C3%BCrer's%20algorithm. – qqqqqqq May 20 '21 at 12:42
To calculate the square root of a floating point number of fixed size you could just precompute a table of the square roots for each floating point number. Retrieving the square root for a given number from that table would be an O(1) algorithm. – winkeldings May 21 '21 at 13:29
There is an uncountable amount of numbers even in the (0; 1) segement. There is no way you can precomput that many numbers. Let alone all real numbers. – qqqqqqq May 21 '21 at 16:59
1

The question is not about real numbers. The Math.Sqrt() function works with floating point numbers with a fixed number of bits. So there is only a finite set of numbers, that we have to work with. If you, however, want to describe an algorithm that accepts real numbers, you cannot assume that the squareroot function is O(1). – winkeldings May 22 '21 at 18:05
Should we consider real numbers and double as two different sets of numbers? – qqqqqqq May 23 '21 at 07:36
1

Yes, they are different. For example, pi or 10^400 cannot be saved as a double. – winkeldings May 24 '21 at 08:15
@qqqqqqq The question is about the complexity of a piece of code, not the complexity of a general algorithm to find square roots of all integer, rational, real, or complex numbers. It takes a single instruction, so it will run about the same amount of time for any input. Of course, if you need to find the square root of a number that doesn't fit in a `double` or `float`, the complexity will be related to something like how many bits are needed to store the number. Multiplication is the same. O(1) unless you need to work with larger numbers. Karatsuba is an example of fast multiplication. – user904963 Jan 02 '22 at 23:13

score 9 · Accepted Answer · edited May 23 '17 at 12:23

9

You can consider it O(1):

In other words, Math.Sqrt() translates to a single floating point machine code instruction

source: c# Math.Sqrt Implementation

edited May 23 '17 at 12:23

Community

1
1

answered Jan 03 '16 at 18:45

BlackBear

22,411
10
48
86

7

I never heard about an algorithm which would be able to find the square root in `O(1)`. Until that algorithm will be added to the answer I am going to downvote the answer. – qqqqqqq May 18 '21 at 16:26
2

Does it take the same number of cycles to compute regardless of the argument? – JAlex May 18 '21 at 17:11
@qqqqqqq: Why don't you just measure it? Anyway, [this](https://scicomp.stackexchange.com/a/2170) answer says that the complexity is comparable to division on most CPUs. If performance is more important than accuracy, then you can try to use something else. Instead of Euclidean distance (I know, OP isn't you) older games such as Doom used simple distance by all coordinates. I also omit square roots (and then squares are unnecessary, too) in image processing when [looking up](https://github.com/koszeggy/KGySoft.Drawing/blob/master/KGySoft.Drawing/Drawing/Imaging/Palette.cs#L738) closest colors. – György Kőszeg May 22 '21 at 21:38
1

@GyörgyKőszeg, sorry but if you suggest me to reason about time complexity using this advice: `Why don't you just measure it?` I have nothing to learn from you. But anyway, thank you for your attempt to be useful. – qqqqqqq May 23 '21 at 07:35
@qqqqqqq: No need to be offended. I provided quite an elaborate answer and also linked a related post. What else do you expect? Nobody's similar links were good enough for you so I really think that doing some measurements can give the satisfying answer. Something like [this](https://dotnetfiddle.net/Hd55Gm). _Please note though that results are architecture-dependent:_ on the fiddle server square root is about 40% slower than the four basic operations (they perform very similarly). On my machine it's just 15% slower though. – György Kőszeg May 23 '21 at 09:12
@GyörgyKőszeg, I meant that it is possible to create such a hardware setup which would compute the sqrt almost instantaneously. But that won't mean anything about the big O estimation. That is why I told that it is not useful for me at all. And I am sorry for being rude. SO made me this way. Here you get downvoted all the time you make a mistake and almost everyone is trying to press you to prevent you from ever asking questions here again. So, I have to be hard if I want to use SO. – qqqqqqq May 23 '21 at 09:21
No worries, I know the feeling, too. – György Kőszeg May 23 '21 at 09:33

Time complexity of Math.Sqrt()?

2 Answers2

Linked