Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Time complexity of Math.Sqrt()?

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.

like image 366
Bathant Hegazy Avatar asked Jan 03 '16 18:01

Bathant Hegazy


People also ask

Is sqrt constant time?

There is no algorithm which would compute a square root in constant time.

Is square root still slow?

sqrt() is "slow," not slow. Fundamentally, the operation is more complex than an addition or division.

What does math sqrt do in Java?

Math. sqrt() returns the square root of a value of type double passed to it as argument. If the argument is NaN or negative, then the result is NaN.

How does sqrt in C work?

The sqrt() function takes a single argument (in double ) and returns its square root (also in double ). The sqrt() function is defined in math. h header file. To find the square root of int , float or long double data types, you can explicitly convert the type to double using cast operator.


1 Answers

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

like image 174
BlackBear Avatar answered Sep 29 '22 09:09

BlackBear