Analisis Pengaruh Base Case pada Algoritma Karatsuba terhadap Tingkat Efisiensi Waktu Eksekusi

Abstract

Algoritma Karatsuba adalah algoritma perkalian yang masih banyak diteliti oleh peneliti Ilmu Komputer dan Matematika meskipun telah berusia lebih dari setengah abad. Algoritma ini merupakan algoritma yang menerapkan konsep Divide and Conquer. Oleh karena itu terdapat nilai base case (BC) yang dapat diganti. Hipotesisnya adalah nilai BC ketika ditingkatkan akan mengurangi waktu eksekusi sampai mencapai suatu nilai x. Setelah melewati nilai x, waktu eksekusi akan bertambah. Pada penelitian ini dilakukan dengan 36 percobaan dengan kombinasi dari 3 pilihan digit, 3 kasus, dan 4 BC. Pilihan digitnya adalah 2000, 4000, dan 6000 digit. Kasus yang digunakan adalah angka acak yang dikalikan dengan angka acak itu sendiri. BC yang digunakan adalah 10^{10^n} dengan nilai n = {0, 1, 2, 3}. Penelitian ini menghasilkan fakta yang berlawanan dengan hipotesis. Semakin besar BC membutuhkan waktu eksekusi yang lebih singkat. Hal ini diduga karena di dalam Python sendiri sudah menerapkan algoritma Karatsuba secara implisit.