Menghitung Kompleksitas binary search

Procedure b_search (Input a₁…a_x: Integer; x: Integer;

                                    Output cari: integer)

Deklarasi

            data: Array[1..20] Of Integer

            i, j, temp, kiri, tengah, kanan, cari, x: Integer

            ketemu: Boolean

Algoritma

            Output(‘Berapa banyak data [maks. 20]? ‘)

            Input(x)

            For i ← 1 To x Do

                        Output(‘Input data ke-‘,data[i])

            EndFor

            For i ← 1 To x Do

                        For j ← x – 1 DownTo i Do

                                    If (data[i] > data[j+1]) Then

                                                temp ← data[i]

                                                data[i] ← data[j+1]

                                                data[j+1] ← temp

                                    EndIf

                        EndFor

            EndFor

Output(‘Data setelah diurutkan:’)

            For i ← 1 To x Do

                        Output(data[i])

            EndFor

            Output(‘Data yang dicari: ‘)

            Input(cari)

            kiri ← data[x]

            kanan ← 1

            ketemu ← False

            While Not(ketemu) Do

                        tengah ← (kiri + kanan) div 2

                        If data[tengah] = cari Then

                                    ketemu ← True

                        ElseIf (cari < data[tengah])

                                    kiri ← tengah – 1

                        Else

                                    kanan ← tengah + 1

                        EndIf

            EndWhile

            If Not(Not(Ketemu)) Then

                        Output(‘Data berada diposisi ke-‘,tengah)

            Else

                        Output(‘Data tidak ditemukan.’)

            EndIf

EndProcedure

·         Banyaknya data adalah a_x, maka x = n.

·         Operasi dasar yang berada dibagian paling dalam adalah operasi “←” (input)

·         Menentukan nilai Tmin(n), Tmax(n) & Tavg(n):

a.       Tmin(n) = 1 + n + [n * (i * 3)]  + n + 4 + [1 * (1 + 1)]

b.       Tmax(n) = 1 + n + [n * (i * 3)]  + n + 4 + [n * (1 + 1) ]

c.       Tavg(n) = 1+n+[n*(i*3)]+n+4+[1*(1+1)]+...+1+n+[n*(i*3)]+n+4+[n*(1+1)]

                                                                           n

Operasi Dasar	Input/“←”
Tmin(n)	1 + n + [n * (i * 3)]  + n + 4 + [1 * (1 + 1)]
Tmax(n)	1 + n + [n * (i * 3)]  + n + 4 + [n * (1 + 1) ]
Tavg(n)	≈ ≈ n