Tugas Ο Ω Ɵ

Operasi dasar yang dipilih Output

Tmin(n) = 1

Tmax(n) = 2n ~ n

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

O

a)      1 ϵ O(n)

t(n) < cg(n)

1 < n

C = 1 N₀ = 1

b)     2n ϵ O(n)

t(n) < cg(n)

2n <  n

Mis n = 1

2.1 <  1 X

Mis n = 2

2.2 <  2 x

Mis n = 10

2.10 <  10 x

Mis n = 100

2.100 <  100 x

Maka  2n <  n  bukan anggota O(n)

c)      1 + 2N/10  ϵ O(n)

t(n) < cg(n)

1 + 2N/10 <  n

MIS N = 1

1+ 2.1/10 <  1 X

MIS N = 2

1+2.2/10 <  2 √

MIS N = 10

1+2.10/10 <  10 √

MIS N = 100

1+ 2.100/10 <  100 √

Maka  1+2n/10 <  n  anggota O(n)

N₀ = 2

C = 1

Ω

a)      1 ϵ Ω (n⁰)

t(n) > cg(n)

1 > n⁰

C = 1 N₀ = 0

b)     2n ϵ Ω(n⁰)

t(n) > cg(n⁰)

2n > n

Mis n = 0

2.0 >  0 √

Mis n = 1

2.1 >  1 √

Mis n = 2

2.2 >  2 √

Mis n = 10

2.10 >  10 x

Mis n = 100

2.100 >  100 x

Maka  2n >  n⁰   anggota Ω (n⁰)

C =  1 N₀ = 0

c)      1 + 2N/10  ϵ Ω(n)

t(n) > cg(n⁰)

1 + 2N/10 >  n⁰

MIS N = 1

1+ 2.1/10 >  1 √

MIS N = 2

1+2.2/10 >  2 X

MIS N = 10

1+2.10/10 >  10 X

MIS N = 100

1+ 2.100/10 <  100 X

Maka   1 + 2N/10  <  n⁰  bukan anggota Ω(n⁰)

tugas analisi

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