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

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

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

- Big Omega (Ω)

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

  T(n) ≥ C g(n)
    2n + 2   ≥  ... n          ( untuk semua n ≥  1 )
    2n + 2   ≥   2n
 C = 2  nₒ = 1

- Big Theta (Θ)

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

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

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

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

  c1 = 4                        c2 = 2               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 = 2n + 2 

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


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


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

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

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

  c1 = 3     c2 = 2     nₒ = 2




Terimakasih Telah Membaca Blog Kami ^_^
(F)