Jabarkan Penerapan pada teori kompleksitas dari Algoritma pencarian biner

Seandainya kita tidak mengetahui sebuah jangkauan yang tetap tempat dari bilangan kberada, kita masih dapat menentukan nilainya dengan mengajukan  pertanyaan ya/tidak dalam bentuk "Apakah k lebih besar dari x?" untuk beberapa bilangan x. Sebagai konsekuensi sederhana dari cara ini, jika kita dapat menjawab pertanyaan "Apakah nilai bilangan bulat k lebih besar dari nilai yang diberikan?" pada suatu waktu kemudian kita dapat menemukan nilai dari bilangan tersebut sama lamanya ditambah dengan faktor log k. Hal ini disebut sebuah reduksi, dan karena disebabkan reduksi ini maka kebanyakan teoris kompleksitas berkonsentrasi pada permasalahan keputusan, algoritme-algoritme yang mengasihlan jawaban sederhana berupa ya/tidak.

Sebagai contoh, anggap kita dapat menjawab "Apakah matriks n x n ini memiliki determinan lebih besar dari k?" dalam waktu O(n2). Kemudian, dengan memanfaatkan pencarian biner, kita dapat menemukan (batas atas) determinan tersebut dalam waktu O(n2log d), dimana d adalah determinan; sebagai catatan, d bukanlah ukuran dari masukan tetapi ukuran dari keluaran.