Permasalahan NP-Complete (Nondeterministic Polynomial-Complete) merupakan masalah yang tidak bisa diselesaikan dengan algoritma konvensional. Hal ini disebabkan karena variasi parameter dan ruang pencarian yang sangat besar.Untuk menyelesaikannya diperlukan algoritma heuristik seperti contohnya algoritma Cuckoo Search. Algoritma cuckoo search telah menunjukkan performansi pencarian yang lebih bagus dari algoritma heuristik lain seperti algoritma Particle Swarm Optimization (PSO) maupun algoritma genetika. Keunggulan dari Cuckoo Search terletak pada random stepnya yang menggunakan Lévy Flight yang memungkinkan pencarian nilai optimal dalam waktu yang lebih singkat. Penelitian ini meninjau performansi algoritma Cuckoo Search dengan menggunakan masalah NP-Complete klasik yaitu Travelling Salesman Problem. Hasil penelitian akan dibandingkan dengan algoritma genetika.Hasil pengujian menunjukkan algoritma Cuckoo Search memiliki efisiensi yang lebih besar bila dibandingkan dengan algoritma genetika. Dari pencarian hasil optimal 180 kota, algoritma Genetika memerlukan waktu kurang lebih 43 menit sedangkan algoritma Cuckoo Search hanya memerlukan waktu 53 detik.