The computational efficiency of cosine similarity versus Euclidean distance depends on whether vectors are normalized and how they're processed. Without normalization, cosine similarity typically requires more operations. It involves three main steps: calculating the dot product (O(n) time), computing the magnitudes of both vectors (each O(n)), and then dividing the dot product by the product of magnitudes. This results in roughly 3n operations for n-dimensional vectors. In contrast, Euclidean distance calculates the squared differences between components (O(n)), sums them, and takes the square root, totaling approximately n operations plus a square root. Thus, raw cosine similarity is roughly three times more computationally intensive than Euclidean distance for unnormalized vectors.
However, normalization changes this dynamic. If vectors are pre-normalized (e.g., scaled to unit length), cosine simplifies to the dot product alone (O(n)), making it faster than Euclidean distance, which still requires O(n) operations to compute the sum of squared differences even after normalization. For example, in text processing with TF-IDF vectors, which are often normalized, cosine similarity becomes highly efficient. Conversely, applying normalization on the fly adds overhead: computing magnitudes (O(n) per vector) and scaling components (O(n)), which might negate any efficiency gains unless done in advance.
Transformations also affect equivalence. Normalized Euclidean distance between vectors relates directly to cosine similarity via the identity ||a - b||² = 2(1 - cos(a, b)) for unit vectors. If squared Euclidean distance is used (avoiding the square root), it becomes 2 - 2*cos(a, b), aligning closely with cosine results but still requiring comparable computation. In practice, the choice depends on context: cosine is preferable for direction-focused tasks with pre-normalized data, while Euclidean better captures magnitude differences. For large-scale applications like clustering, preprocessing costs and metric semantics (direction vs. magnitude) often dictate the optimal choice more than raw computational differences.