Jabarkan function fpb(a, b) dari Algoritme Euklides

Efisiensi komputasional algoritme Euklides telah dipelajari secara menyeluruh. Efisiensi ini bisa diartikan sebagai banyak langkah pembagian yang perlu dilakukan algoritme, dikali dengan harga komputasi setiap pembagian. Analisis tertua yang diketahui tentang algoritme Euklides berasal dari A. A. L. Reynaud pada tahun 1811, yang menunjukkan bahwa banyak langkah pembagian yang dilakukan dengan masukan  tidak mungkin lebih dari ; dia kemudian memperbaiki batas ini menjadi . Kemudian, pada tahun 1841, P. J. E. Finck menunjukkan bahwa banyak langkah pembagian tidak mungkin lebih tinggi dari , dan artinya algoritme Euklides berjalan dalam waktu polinomial dari ukuran masukannya. Émile Léger, pada tahun 1837, mempelajari kasus terburuknya, yaitu ketika masukannya adalah bilangan Fibonacci yang bersebelahan. Analisis Finck kemudian diperbaiki oleh Gabriel Lamé pada tahun 1844, yang menunjukkan bahwa banyak langkah yang diperlukan untuk menyelesaikan algoritme tidak pernah lebih dari lima kali banyak digit bilangan yang lebih kecil .