Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation This could relate to different applications, but my application of interest is in similarity-search systems based on high-dimensional feature vectors. In these systems, since search  based on Euclidean distance is costly, the vectors are encoded as binary vectors. Then the search is done based on Hamming distance computation which is supposed to be faster than the Euclidean counterpart. My question is, practically, how much is this speed-up for an average architecture? 

More formally, suppose we have a database $\mathrm{X} = [\mathbf{x}_1, \cdots, \mathbf{x}_i, \cdots, \mathbf{x}_N]$ of $N$ vectors of dimension $n$, and a vector $\mathbf{y}$ of the same dimensionality. Now imagine two cases:


Vectors are real-valued, i.e., $\mathbf{x}_i \in \Re^n$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Euclidean distance to $\mathbf{y}$, i.e.:


\begin{equation}
i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} ||\mathbf{y} - \mathbf{x}_i||_2.
\end{equation}


Vectors are binary, i.e., $\mathbf{x}_i \in \mathcal{B}^n$ with $\mathcal{B} = \{0,1\}$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Hamming distance to $\mathbf{y}$, i.e.: 


\begin{equation}
i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} \sum_{j=1}^n \big( \mathbf{y}(j) \oplus \mathbf{x}_i(j) \big),
\end{equation}
where $\oplus$ denotes the XOR operation.

Both of these operations have complexity of $\mathcal{O}(Nn)$. However, the real case requires doing the operations in floating-point arithmetic while the binary case enjoys the fixed-point binary operations which are faster.

My question is, in practice, how are these complexities different? Can we say, very roughly though, that they have different constant factors and the ratio of these factors is a constant value? What would that constant value be then? Around 10 or 100 maybe? And how much is it architecture dependent?
The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption).  The practical running time may be different.  Asymptotics ignores constant factors, but constant factors can be important in practice.

The way to tell how much faster it is in practice is to implement it and do some experiments, i.e., benchmark it on realistic workloads.  Asymptotic analysis probably won't be very helpful in this case for predicting how much faster it will be.  No one is likely to be able to give you a prediction for what the results of those experiments will be; you'll just have to try it and see.