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)