Mencari T(n) dari Pseudocode Binary Search

Binary Search

function binary(cari: integer)→integer

{I.S. :}

{F.S. :}

Kamus

        awal,akhir,tengah: integer

        ketemu:boolean

        indeksxx: integer

Algoritma

        awal← 1

        akhir← n

        ketemu ←false

        indeksxx ← 0

        while ((awal ≤ akhir) and (not ketemu)) do

                tengah← (awal+akhir) div 2

                if cari = data[tengah] then

                        ketemu ← true

                        indeksxx ← tengah

                else

                        if cari < data[tengah] then

                             akhir ←  tengah-1

                        else

                              awal ← tengah+1

                         endif

                endif

 endwhile

        binary←indeksxx

endfunction

Menghitung Tmin, Tmax, dan Tavg

Operasi Dasar	C(n)
←	4n+5
≤	n+1
+	2n
Div	n
<	n
=	n
-	n

Tmin dan Tmax pada if =

                                    Min = 1

                                    Max = 1

Tmin dan Tmax pada while =

                                    Min = 1

                                    Max = n

Tmin(n)                = 1+5 = 6

Tmax(n)               = n+5

Tavg(n)                 = 6 + 7 + 8 + . . . + (n+5)  ≈ n

                                                  n

О(Big Oh)	Ω(Big Omega)	ʘ(Big Theta)
Tmin(n) = 6	Tmin (n) = 6	Tmin (n) = 6
О = t(n) € О(g(n)) ; t(n) ≤ Cg(n)	Ω = t(n) € (g(n)) ; t(n) ≥ Cg(n)	ʘ = t(n) € ʘ (g(n)) ; C2 g(n) ≤ t(n) ≤ C1 g(n)
Tmin(n) = 6 € О (1)	Tmin(n) = 6 € Ω (1)	Batas atas     = 6 € О (1)
Jadi	Jadi	Batas Bawah = 6 € Ω (1)
n0  = 0	n0 = 0	Jadi = n0 = 0
C   = 1	C = 1	C1 = 1, C2 = 1

Tmax = n + 5 

О(Big Oh)

О = t(n) € О(g(n)) ; t(n) ≤ Cg(n)

        n + 5 € О (n)

n + 5 ≤ 5n                                                                        

×        5   ≤ 0            → n = 0

×        6   ≤ 5            → n = 1

(b)    7   ≤ 10            → n = 2

(b)    8   ≤ 15            → n = 3

(b)    105 ≤ 500        → n = 100

(b)  1005 ≤ 5000       → n =1000

Jadi n₀ = 2

C = 5

Ω(Big Omega)

Ω = t(n) € (g(n)) ; t(n) ≥ Cg(n)

       n + 5 € Ω (n)

        n + 5 ≥ n

(b)  5 ≥ 0              → n = 0

(b)  6 ≥ 1              → n = 1

(b)  7 ≥ 2              → n = 2

(b)  105 ≥ 100      → n = 100

(b)  1005 ≥ 1000  → n = 1000

Jadi n₀ = 0

                C = 1

ʘ(Big Theta)

ʘ = t(n) € ʘ (g(n)) ; C₂ g(n) ≤ t(n) ≤ C₁ g(n)

Batas Atas = n + 5 ≤ 5n   = n₀ = 2, C₁ = 5

Batas Bawah = n + 5 ≥ n = n₀ = 0,  C₂ = 1

Jadi n0 = 2, C1 = 5, C2 = 1

Tavg  (n)          = 6 + 7 + 8 . . . + (n + 5)
                                             n

                            = ½ n ( 6 + (n + 5 ))/n

                            = ½ (n+11)

                            = n/2 + 11/2 == ½ + 11/n

О(Big Oh)

О = t(n) € О(g(n)) ; t(n) ≤ Cg(n)

½n + 11/2 € О(n)

½n + 11/2 ≤ 4n

×        11/2 ≤ 0          → n = 0

×        6       ≤ 4         → n = 1

(b)    13/2 ≤ 8            → n = 2

(b)    7       ≤ 12         → n = 3

(b)  111/2 ≤ 400        → n = 100

(b)  1011 ≤ 4000       → n = 1000

Jadi n₀ = 2

C = 4

Ω(Big Omega)

Ω = t(n) € (g(n)) ; t(n) ≥ Cg(n)

1/2n + 11/2 € Ω (n)

1/2n + 11/2 ≥ n

(b) 11/2 ≥ 0          → n = 0

(b) 12/2 ≥ 1          → n = 1

(b) 13/2 ≥ 2          → n = 2

(b) 14/2 ≥  3         → n = 3

 ×     111/2 ≥ 100  → n = 100

Jadi n₀ = 0

                C = 1

ʘ(Big Theta)

ʘ = t(n) € ʘ (g(n)) ; C₂ g(n) ≤ t(n) ≤ C₁ g(n)

Batas Atas = 1/2n + 11/2 ≤ 4n  

Jadi = n₀ = 2, C₁ = 4

Batas Bawah = 1/2n + 11/2 ≥ n

Jadi = n₀ = 0,  C₂ = 1

Jadi n0 = 2, C1 = 4, C2 = 1