I have to find computational complexity of an expression for Euclidean distance

d(x,y)= {(x1-x2)^2 + (y1-y2)^2}^1/2

But I have certain confusion because of which I am unable to proceed. Firstly there are two variables. Secondly since there is a root ,what will be its effect? If there were no roots, I can understand its worst case complexity would have been O(n^2).

I will really appreciate if someone can enlighten me in this regard Thanks in advance for your spending valuable time!

  • Update

I assume that my program will run on abstract machine RAM.

  • $\begingroup$ How did you get $O(n^2)$? What are the units? instructions? bit-operations? What is $n$ here? What is the model of computation? Are you really asking what is the complexity of computing the square root? That might be a more useful question (more likely to be useful to others in the future). How many bits of precision do you want the answer to have? $\endgroup$ – D.W. Dec 7 '17 at 6:05
  • $\begingroup$ Your update still doesn't answer most of my questions. $\endgroup$ – D.W. Dec 7 '17 at 7:09

The computational complexity depends on what you want to measure. If you you're doing this computation on a common computer with floating point arithmetic, then you can estimate it mi $O(1)$, because every floating point operation (addition, multiplication and square root) is in $O(1)$.

If you use fixed point arithmetic for $n$-bit numbers, then addition can be done in $O(n)$, multiplication in $O(n^2)$, and square root in $O(n^2)$ steps (Note: For multiplication and addition are existing better bounds). Putting this together, you will add two $O(n)$-bit numbers and take the square root of the result which gives $O(n^2)$ steps.

As you can see, the runtime depends on the arithmetic used, and arithmetic determines what $n$ means. If you use $n$-bit complex number in a $n$ dimensional vector space (where $x^2$ denotes the scalar product), you probably will get other estimates.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.