Notasi Asimtotik 1

1. Ο-Notation --> t(n)  ϵ Ο(g(n)) jika t(n)  ≤ cg(n) karena mendekati hasil melalui grafik(g(n)) dari atas.

2. Ω-Notation --> t(n)  ϵ Ω(g(n)) jika t(n)  ≥ cg(n) karena mendekati hasil melalui grafik(g(n)) dari bawah.

3. Θ-Notation --> t(n)  ϵ Θ(g(n)) jika c2g(n) ≤ t(n) ≤ c1g(n) karena mendekati hasil melalui grafik(g(n)) dari atas dan bawah (lebih akurat).

Contoh diambil dari t(n) Postingan sebelumnya\

Cari Minimum

Tmax(n)  : N

Tmin(n)   : 1

Tavg(n)   :  N

Tmax(n) / Worst Case

a.       Ο-Notation n ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

C_2g(n) ≤ Tavg(n) ≤ C₁g(n)

Batas Atas :

t(n) ≤ C(g(n))

t(n) ≤ C(n)

n  ≤ n (untuk semua n ≥ 0)

n  ≤ n­²

C₁:1 n₀: 0

Batas Bawah

t(n) ≥ C(g(n))

t(n) ≥ C(n)

n  ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

a.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

c:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

c:1 n₀: 0

Tavg(n) / Average Case

a.       Ο -Notation n ϵ Ω(g(n))

t(n) ≤ C(g(n))

t(n) ≤ C(n²)

n  ≤ n²

C= 1 ; n₀= 0

b.      Θ-Notation n ϵ Θ(g(n²))

C_2g(n) ≤ Tavg(n) ≤ C₁g(n)

Batas Atas :

t(n) ≤ C(g(n))

t(n) ≤ C(n)          

n  ≤ n (untuk semua n ≥ 0)

n  ≤ n­²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ C(g(n))

t(n) ≥ C(n)

n  ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω -Notation n  ϵ Ο(g(n²))

t(n) ≤ C(g(n))

t(n) ≤ C(n)

n  ≤ n (untuk semua n ≥ 0)

n  ≤ n²

C1:1 n0: 0

Function Palindrom

Tmax(n)  : 3 + N

Tmin(n)   : 6

Tavg(n)   : N  

Tmax(n) / Worst Case

a.       Ο-Notation 3+n ϵ Ο(g(n²))

t(n) ≤ cg(n)

3+n ≤ n + n

3+n ≤ 2n  (untuk semua n ≥ 3)

2n ≤ 2n²

C:2 n0: 3

b.      Θ-Notation 3+n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

3+n ≤ n + n

3+n ≤ 2n  (untuk semua n ≥ 3)

2n ≤ 2n²

C₁:2 n₀: 3

Batas Bawah

t(n) ≥ cg(n)

3+n ≥ n

C₂:1 n₀: 0

C₁: 2 C₂:1 n₀: 3

c.       Ω-Notation 3+n ϵ Ω(g(n))

t(n) ≥ cg(n)

3+n ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 6 ϵ Ο(g(n²))

t(n) ≤ cg(n)

6     ≤ n

6     ≤ n  (untuk semua n ≥ 6)

n     ≤ n²

C:1 n0: 6

              

b.      Θ-Notation 6 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

6     ≤ n

6     ≤ n  (untuk semua n ≥ 6)

n     ≤ n²

C₁:1 n0: 6

Batas Bawah

t(n) ≥ cg(n)

6     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 6

c.       Ω-Notation 6 ϵ Ω(g(n))

t(n) ≥ cg(n)

6     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

b.      Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

c.       Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

d.      Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Sisip Belakang

Tmax(n)  : N

Tmin(n)   : 1

Tavg(n)   :  N

Tmax(n) / Worst Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Hapus Belakang

Tmax(n)  : N

Tmin(n)   : 1

Tavg(n)   :  N

Tmax(n) / Worst Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

a.       Ο-Notation n  ϵ Ο(g(n²))

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C:1 n0: 0

b.      Θ-Notation n ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

n    ≤   n

n    ≤ n  (untuk semua n ≥ 0)

n    ≤  n²

C₁:1 n0: 0

Batas Bawah

t(n) ≥ cg(n)

n     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 0

c.       Ω-Notation n ϵ Ω(g(n))

t(n) ≥ cg(n)

n     ≥ n

C:1 n₀: 0

Tampil Linked List

Tmax(n)  : 1

Tmin(n)   : 1

Tavg(n)   :  1

Tmax(n) / Worst Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tmin(n) / Best Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1   ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0

Tavg(n) / Average Case

a.       Ο-Notation 1 ϵ Ο(g(n²))

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C:1 n0: 1

b.      Θ-Notation 1 ϵ Θ(g(n²))

Batas Atas

t(n) ≤ cg(n)

1    ≤ n

1   ≤  n  (untuk semua n ≥ 1)

n   ≤ n²

C₁:1 n0: 1

Batas Bawah

t(n) ≥ cg(n)

1     ≥ n

C₂:1 n₀: 0

C₁: 1 C₂:1 n₀: 1

c.       Ω-Notation 1ϵ Ω(g(n))

t(n) ≥ cg(n)

1     ≥ n

C:1 n₀: 0