Notasi Asimtotik dari worst case, best case dan average case program segitiga pascal

Program Segitiga_pascal

kamus 

i,j,n : Integer

    p   : array [1..50,1..50] of integer

Algoritma

  read(n);

  for i ß 1 to n do

       for j ß 1 to i do

           if (j =1) or (j = i)
                then
                                p[i,j] ß 1

                else

                                p[i,j] ß p[i-1,j] + p[i-1,j-1]

           write(p[i,j],'    ')

       Endif

  Endfor  Endfor

Terdalam (+)

Tmin  = 0

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
0 ≤ n
n = 0               0 _≤ 0
n = 1               0 ≤ 1
n = 6               0 ≤  6
n = 100                            0  ≤  100  

n₀ = 0
C = 1

Notasi ꭥ

t(n)  C ꭥ (g(n))
t(n) ≥ ꭥ (g(n))
0 ≥ -n
n = 0               0 _≥ 0
n = 1               0 ≥ -1
n = 5               0 ≥  -5
n = 1000    0 ≥  -1000                    

n₀ = 0
C = -1

Notasi θ

t(n)  C θ (g(n))
 C₂ ꭥ (g(n)) ≤  t(n)  ≤ C₁ O(g(n))

batas atas
C₂  ꭥ (g(n)) ≤ t(n) (untuk semua n ≥ 0)
n - ≤ 0
C₂ = -1
n₀ = 0

batas bawah
t(n)  ≤ C₁ O(g(n)) (untuk semua n ≥ 0)
0 ≤ n
C₁ = 1
n₀ = 0

C₁ = 1 C₂ = -1 n₀ = 0

Tmax = n - 2

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
n-2 ≤ n
n = 0               -2 _≤ 0
n = 1               -1 ≤ 1
n = 6               4 ≤  6
n = 100                            98  ≤  100                       

n₀ = 0
C = 1

Notasi ꭥ

t(n)  C ꭥ (g(n))
t(n) ≥ ꭥ (g(n))
n-2 ≥ ½ n
n = 0               -2 _≥ 0  false
n = 1               -1 ≥ 0.5 false
n = 4               2 ≥  2
n = 5               3 ≥  2.5
n = 1000    9998 ≥  500                

n₀ = 4
C = 1/2

Notasi θ

t(n)  C θ (g(n))
 C₂ ꭥ (g(n)) ≤  t(n)  ≤ C₁ O(g(n))

batas atas
C₂  ꭥ (g(n)) ≤ t(n)           (untuk semua n ≥ 4)
½ n  ≤ n-2
C₂ = 1/2
n₀ = 4

batas bawah
t(n)  ≤ C₁ O(g(n))            (untuk semua n ≥ 0)
n - 2 ≤ n
C₁ = 1
n₀ = 0

C₁ = 1 C₂ = 1/2 n₀ = 4

Tavg  = (n – 2) / 2

          ≈  n – 2

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
n/2 - 1 ≤ n
n = 0               -1 _≤ 0
n = 1               -1 ≤ 1
n = 6               2 ≤  6
n = 100                            51  ≤  100                       

n₀ = 1
C = 1

Notasi ꭥ

t(n)  C ꭥ (g(n))
t(n) ≥ ꭥ (g(n))
n/2 - 1  ≥  ¼ n
n = 0               -1 _≥ 0  false
n = 1               - ½ ≥ ¼ false
n = 4               1 ≥  1
n = 8               3 ≥  2
n = 1000    499 ≥ 250                    

n₀ = 4
C = ¼

Notasi θ

t(n)  C θ (g(n))
 C₂ ꭥ (g(n)) ≤  t(n)  ≤ C₁ O(g(n))

batas atas
C₂  ꭥ (g(n)) ≤ t(n)           (untuk semua n ≥ 4)
¼ n  ≤ n/2 - 1
C₂ = ¼
n₀ = 4

batas bawah
t(n)  ≤ C₁ O(g(n))            (untuk semua n ≥ 0)
n/2 - 1  ≤ n
C₁ = 1
n₀ = 0

C₁ = 1 C₂ = ¼  n₀ = 4