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⁰)