Asymptotic Notation

  • Menggambarkan karakteristik/perilaku suatu algoritma pada batasan tertentu (berupa suatu fungsi matematis)
  • Dituliskan dengan notasi matematis yg dikenal dgn notasi asymptotic
  • Notasi asymptotic dapat dituliskan dengan beberpa simbul berikut  Θ , Oo, Ω, ω
  • Mendefinisikan himpunan fungsi ;
  • Pada prakteknya untuk membandingan 2 ukuran fungsi.
  • Notasi menggambarkan perbedaan  rate-of-growth hubungan antara definisi fungsi dan definisi himpunan fungsi.

 

 

Θ– Notation (Notasi Big – Theta)

Merupakan notasi asymptotic untuk batas atas dan bawah.

untuk fungsi  g(n),  Θ(g(n)) adalah himpunan fungsi f (n) didefinisikan sebagai berikut:

 

Θ (g (n)) : {f (n): adalah nilai konstanta positif c1, c2 dan nsehingga  0 < c1g(n)  f (n) < c2g(n) untuk semua n > n0}

Untuk menunjukkan bahwa f (n) adalah anggota dari Θ(g(n))

g(n) adalah asymptotically tight bound untuk  f(n).

atau dapat dikatakan bahwa Θ (big-theta) adalah tight-bound dari suatu fungsi

 

 

 

 

Contoh :

  1. ½ n2 – 3n = Θ(n2)

Jawab :

 

0 < c1g(n)  f (n) < c2g(n)

c1n2 < ½ n2 – 3n < c2n2

c1 <    –    < c2

c1 =

c2  = 

n = 7

 

 

O-Notation (Big-Oh Notation)

asimtotik notasi Big-Theta (Θ) merupakan  batas fungsi dari atas dan bawah. Ketika kita hanya memiliki asimtotik batas atas, kita menggunakan notasi O (Big-Oh)

Untuk fungsi g(n),kita definisikan O(g(n)) sbg big-Oh dari n, sbg himpunan:

O (g (n)) = {f (n):  konstanta c dan n0 positif sedemikian sehingga 0 < f(n) < c g(n) untuk semua n> = n0}

 

f(n) = Θ(g(n)) mengisyaratkan bahwa f(n) = O (g(n)) selama Θ-notation adalah lebih kuat daripada O-notation

 

 

Contoh :

n2 – 3n = O(n2)

0 < f(n) < c g(n)

0 <  n2 – 3n < c n2

0 <   –     < c

c =   

n = 7

 

 

Ω – Notation

 

Ω – Notation memberikan batas bawah asimtotik
Ω (g (n)) = {f (n): terdapat konstanta c dan n0 positif sedemikian sehingga 0 < c g(n) < f (n) untuk semua n >n0}

Contoh

  1. 7n2 = Ω(n)

Jawab

< c g(n) < f (n)

0 < c n < 7n2

0 < c < 7n

c = 7

n = 1

 

Theorema :
Untuk setiap fungsi f (n) dan g (n), kita memiliki
f (n) = Θ (g (n)) jika dan hanya jika
f (n) = O (g (n)) dan
f (n) = Ω (g (n))

Kami biasanya menggunakan teorema ini untuk membuktikan batas asimtotik ketat daribatas asimtotik atas dan bawah

o-notation (little-oh notation)

Asymptotic upper bound disediakan  oleh O-notation  mungkin bukan merupakan  tight-asymptotic
2n2  = O (n2) adalah tight asymptotic, namun

2n  = O (n2) tidak !

 

o-notation untuk menunjukkan sebuah batas atas yang tidak secara ketat terikat (not asymptotically tight)

 

o (g (n)) = {f (n): untuk setiap konstanta positif c > 0, terdapat n0 konstan > 0 sedemikian sehingga 0 < f (n) < cg(n) untuk semua n > n0}

 

ω -notation

kita menggunakan ω -notation untuk menunjukkan batas bawah yang not asymptotically tight

f (n) = ω (g (n)) jika dan hanya jika g (n) = O (f (n))

ω (g (n)) = {f (n): untuk setiap konstanta positif c > 0, terdapat n0 konstan> 0 sedemikian sehingga 0<  c g (n) <f (n) untuk semua n > n0}