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.

Odellodella

Just wondering, shouldn't that for statement be of a time complexity of O(n) as it effectively iterates over an array? – Twelfth

No, it's O(13), array size is fixed, so O(1) actually. – Zonation

sqrtd reference, which what is likely how Math.Sqrt() is computed. – Pianist

Answer 1

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

Cyaneous

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. – Sportsman

Does it take the same number of cycles to compute regardless of the argument? – Pianist

@qqqqqqq: Why don't you just measure it? Anyway, this 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 closest colors. – Kaleb

@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. – Sportsman

@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. 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. – Kaleb

@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. – Sportsman

No worries, I know the feeling, too. – Kaleb

Answer 2

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.

Whitesell

There is no algorithm which would compute a square root in constant time. cstheory.stackexchange.com/questions/9706/…. – Sportsman

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. – Whitesell

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. – Sportsman

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). – Whitesell

Should we consider real numbers and double as two different sets of numbers? – Sportsman

Yes, they are different. For example, pi or 10^400 cannot be saved as a double. – Whitesell

@Sportsman 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. – Sundries