# Why is the time complexity of the Triplet Loss $O(N^3)$

The triplet loss function uses an anchor, positive, and negative examples. If $$N$$ are the number of examples in the training set with $$C$$ classes, then I think that the time complexity should be $$O(NN_cN_{c'})$$ not $$O(N^3)$$ from Probabilistic Machine Learning, Murphy (2022)

Naively minimzing the triplet loss takes $$O(N^3)$$ time

Because for every example in the training set, we have $$N_c$$ possible positive examples in a class $$C=c$$ and $$N_{c'}$$ possible negative examples not in class $$C=c$$

(I've seen other research papers used that however with a modification in the denominator: $$\mathcal{O}(N^3/C)$$, where $$C$$ is the number of classes)

• Can you please provide source tha claims that the complexity is $O(N^3)$?
– nbro
Commented Jul 10, 2022 at 10:57
• @nbro In "Probabilistic Machine Learning, Murphy (2022)" - "Naively minimzing the triplet loss takes $O(N^3)$ time". I've seen other research papers used that however with a modification in the denominator: $O(N^3/C)$ where $C$ is the number of classes Commented Jul 10, 2022 at 11:06
• Please, edit your post to include all this info directly there.
– nbro
Commented Jul 10, 2022 at 11:10

For each anchor data point $$x_i^a$$ in class $$j$$, the intra-distance should be computed $$g_j$$ times, where $$g_j$$ is the sample size of that class and the inter-distance should be computed as $$N$$ times, where $$N$$ is the sample size of the dataset. In other words, for each data point, the triplet loss computes all possible distance between the intra-distance and the inter-distance, and the computation cost for $$x_i^a$$ should be $$g_i \cdot N$$.

For the dataset, the total computation cost is $$\Sigma_j^c (g_j^2 \cdot N)$$.

\begin{align*} O(*) &= \Sigma_j^c (g_j^2 \cdot N) \\ &= N \cdot \Sigma_j^c g_j^2 \\ \end{align*}

According to the arithmetic mean and quadratic mean inequality[28], $$\frac{\Sigma_i^n x_i}{n} \leq \sqrt{\frac{\Sigma_i^n x_i^2}{n}}$$, when $$x_1 = x_2 = x_3 ... = x_n$$ the arithemtic mean is equal to the quadratic mean.

Therefore,

\begin{align*}N \cdot (\frac{\Sigma_j^c g_j}{c})^2 \cdot c &\leq O(*) < N \cdot \Sigma_j^c N^2 \\N \cdot \frac{N^2}{c} &\leq O(*) < c \cdot N^3 \\ \frac{N^3}{c} &\leq O(*) < c \cdot N^3\\\end{align*}

The lower boundary of $$O(*)$$ is consistent with the paper result.