Notasi Asimptotik (Big Oh (O), Big Omega (Ω) , Big Theta (Θ) )

Menghitung Big Oh (O), Big Omega (Ω) , Big Theta (Θ)

~) Tmin = 4
- Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    4    ≤  ... n          ( untuk semua n ≥  1 )
    4    ≤  4n
 C = 4  nₒ = 1

- Big Omega (Ω)

  T(n) ε Ω (g(n))

  T(n) ≥ C g(n)
    4    ≥  ... n          ( untuk semua n ≥  1 )
    4    ≥  0 n
 C = 0  nₒ = 1

- Big Theta (Θ)

  T(n) ε Θ (g(n))

  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    4    ≤  ... n          ( untuk semua n ≥  1 )
    4    ≤  4 n

  Batas Bawah
   4    ≥  ... n          ( untuk semua n ≥  1 )
   4    ≥  0 n

  c1 = 4      c2 = 0     nₒ = 1

~) Tmax = n + 2 

- Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    n + 2    ≤  ... n          ( untuk semua n ≥  2 )
    n + 2    ≤  2 n
 C = 2  nₒ = 2


- Big Omega (Ω)
  T(n) ε Ω (g(n))
  T(n) ≥ C g(n)
    n + 2    ≥  ... n          ( untuk semua n ≥  2 )
    n + 2    ≥  1 n
 C = 1  nₒ = 2


- Big Theta (Θ)
  T(n) ε Θ (g(n))
  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    n + 2    ≤  ... n          ( untuk semua n ≥  2 )
    n + 2    ≤  2 n

  Batas Bawah
   n + 2    ≥  ... n          ( untuk semua n ≥  2 )
   n + 2    ≥  1 n

  c1 = 2      c2 = 1     nₒ = 2

~) Tavg = 4n + 2 

  - Big Oh (O)
  T(n) ε O (g(n))
  T(n) ≤ C (g(n))
    4n + 2    ≤  ... n          ( untuk semua n ≥  2 )
    4n + 2    ≤  5 n
 C = 5  nₒ = 2


- Big Omega (Ω)
  T(n) ε Ω (g(n))
  T(n) ≥ C g(n)
   4n + 2    ≥  ... n          ( untuk semua n ≥  2 )
   4n + 2    ≥  4 n
 C = 4  nₒ = 2


- Big Theta (Θ)
  T(n) ε Θ (g(n))
  c2g(n) ≤ t(n) ≤ c1g(n)

  Batas Atas 
    4n + 2    ≤  ... n          ( untuk semua n ≥  2 )
    4n + 2    ≤  5 n

  Batas Bawah
   4n + 2    ≥  ... n          ( untuk semua n ≥  2 )
   4n + 2    ≥  4 n

  c1 = 5      c2 = 4     nₒ = 2

Read More

Kompleksitas Waktu (Best Case, Worst Case, Average Case)

Menganalisis kompleksitas waktu pada sebuah algoritma :

Pada Analisis Algoritma kali ini menggunakan operasi dasar (assigment) karena tanda assigment tersebut paling banyak pada algoritma diatas. Kompleksitas Waktu dibeda atas 2 macam, yaitu : 

 - Best Case Efficiency [Tmin(n)]

   Tmin(n) = 2

 - Worst Case Efficiency [Tmax(n)]

   Tmax(n) = n + 2 ≈ n

 - Average Case Efficiency [Tavg(n)]

   Tavg(n) = (2+3+4+ … +(n+2))/n

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

                    = 1/2 (2n+4) / n

                    = 2/2 n + 2

                     ≈ 4/2 n

                 ≈ 2n

Read More

Kompleksitas Waktu (Best Case, Worst Case, Average Case)

 Algoritma menentukan tipe angka

DEKLARASI

      Angka : integer

DESKRIPSI

      Read (angka)

      IF angka > 0 THEN

                  Write (‘angka positif’)

      ELSE

                  IF angka < 0 THEN

                              Write (‘angka negatif’)

                  ELSE

                              Write (‘angka nol’)

      ENDIF.

T(n) = n+2

T(n)= n

Tmax = 3

Tmin = 2

Taverage = (3+2)/2=3

Read More

Kompleksitas Waktu (Best Case, Worst Case, Average Case)

Algoritma menentukan tipe angka

DEKLARASI

      Angka : integer

DESKRIPSI

      Read (angka)

      IF angka > 0 THEN

                  Write (‘angka positif’)

      ELSE

                  Write (‘angka bukan positif’)

      ENDIF.

T(n) = n

Tmax = 2

Tmin = 1

Taverage = (2+1)/2 = 1

Read More