Tugas Notasi Asimtotik: algoritma login sederhana

Program Login_Sederhana

Kamus

     Const

           user = “ahuy”

           pass = “lima”

           n = 3

     user, pass : string

     n, i : integer

Algoritma

     i <-- 1

     While (i <= n) do

           Input(user)

           Input(pass)

           If (username = user) and (password = pass)

then

                     Output (“login berhasil”)

                Else

                     Output (“login gagal”)

                     i <-- i + 1

           EndIf

     EndWhile

     Output (“kesempatan sudah 3 kali”)

Operasi dasar

<--

<=

+

Operasi dasar yang dipilih Output

Tmin(n) = 1

Tmax(n) = 2n ~ n

Tavg    = (1 + 2n) / 2 ~ 2n /2 ~ 2n ~ n

Big O

            T(n) <= g(n^2)

a.    n = 2

(1 + 2.2) / 2 <= 2^2

2.5 <= 4

b.    n = 5

(1 + 2.5) / 2 <= 5^2

5.5 <= 25

c.     n = 10

(1 + 2.10) / 2 <= 10^2

10.5 <= 100

Big Omega

            T(n) >= g(n)

a.    n = 1

(1 + 2.1) / 2 >= 1

1.5 >= 1

b.    n = 5

(1 + 2.5) / 2 >= 5

5.5 >= 5

c.     n = 10

(1 + 2.10) / 2 >= 10

10.5 >= 10

Big Theta

            Omega(g(n)) <= t(n) <= O(g(n))

a.    n = 1

1 <= (1 + 2.1) / 2 <= 1

1 <= 0.5 <= 1

b.    n = 2

2 <= (1 + 2.2) / 2 <= 2

2 <= 1.5 <= 2

c.     n = 5

5 <= (1 + 2.5) / 2 <= 5

5 <= 5.5 <= 5

d.    n = 10

10 <= (1 + 2.10) / 2 <= 10

10 <= 5.5 <= 10

Omega(g(n^2)) <= t(n) <= O(g(n^2))

a.    n = 1

1^2 <= (1 + 2.1) / 2 <= 1^2

1 <= 0.5 <= 1

b.    n = 2

2^2 <= (1 + 2.2) / 2 <= 2^2

4 <= 1.5 <= 4

c.     n = 5

5^2 <= (1 + 2.5) / 2 <= 5^2

25 <= 5.5 <= 25

d.    n = 10

10 <= (1 + 2.10) / 2 <= 10

10 <= 5.5 <= 10