Rosenkrantz et al. showed that the NN algorithm has the approximation factor Θ ( log ⁡ | V | ) {\displaystyle \Theta (\log |V|)} for instances satisfying the triangle inequality.
Rosenkrantz et al. au arătat că algoritmul NN are factor de aproximare Θ ( log ⁡ | V | ) {\displaystyle \Theta (\log |V|)} pentru cazuri ce satisfac inegalitatea triunghiului.