Jelaskan Kompleksitas komputasi dari Logaritma biner

Logaritma biner juga sering muncul dalam analisis algoritma, bukan hanya karena aritmetika bilangan biner kerap digunakan dalam algoritma, tetapi juga karena logaritma biner muncul dalam analisis algoritma yang menggunakan percabangan dua arah. Jika suatu masalah awalnya punya  pilihan untuk dipilih, dan setiap pengulangan algoritma membagi dua banyak pilihannya, maka banyak pengulangan yang diperlukan untuk mendapatkan satu pilihan adalah bagian bulat dari . Ide ini digunakan dalam menganalisis beberapa algoritma dan struktur data. Contohnya, dalam pencarian biner, ukuran masalah dibagi dua pada setiap pengulangannya, sehingga perlu kira-kira  pengulangan untuk mendapatkan masalah berukuran 1, yang bisa diselesaikan dalam waktu konstan. Tidak jauh berbeda, pohon pencarian biner yang seimbang dan memiliki n element pasti punya tinggi .

Namun, lama waktu dijalankannya algoritma biasanya diekspresikan dalam notasi O besar, yang mengabaikan faktor konstanta. Karena , dengan  adalah suatu bilangan yang lebih dari 1, algoritma yang berjalan dalam waktu  bisa juga dikatakan berjalan dalam waktu . Jadi basis logaritma dalam ekspresi-ekspresi seperti  atau  tidaklah penting. Akan tetapi, dalam beberapa konteks, basis logaritma perlu dijelaskan. Contohnya  tidak sama dengan  karena yang pertama sama dengan  sedangkan yang kedua sama dengan .

Algoritma dengan waktu jalan  terkadang disebut linearitmik. Contoh algoritma dengan waktu jalan  atau  di antaranya:

Waktu rata-rata dari quicksort dan beberapa algoritma pengurutan lainnya

Pencarian dalam pohon pencarian biner yang seimbang