Trying to find Worst Case complexity

Question

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.

Answer 1

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.