Notasi Asimtotik Dari Worst case, Best case,dan Average case Program Faktorial

program Faktorial

kamus

   n,fak,i : integer

Algoritma

       read(n)

       fak ß 1

       for i ß n downto 1 do

                fak ß fak * i 

                write(i)

                if   i = 1

                   then

                            write('')

                   else

                            write('*')

                endif

           endfor

terdalam (write)

TMin   = 2n ≈ n

Notasi O

t(n)  CO(g(n))
t(n) ≤ O(g(n))
2n ≤ 3n
n = 0               0 _≤ 0
n = 1               2 ≤ 3
n = 3               6 ≤ 9
n = 100    200  ≤  300                    

n₀ = 0
C = 3 

Notasi ꭥ

t(n)  C ꭥ (g(n))
t(n) ≥ ꭥ (g(n))
2n ≥ n
n = 0               0 _≥ 0
n = 1               2 ≥ 1
n = 5               10 ≥ 5
n = 100    200  ≥  100                    

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 ≤ 2n
C₂ = 1
n₀ = 0

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

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

TMax  = 2n ≈ n

Notasi O 

t(n)  CO(g(n))
t(n) ≤ O(g(n))
2n ≤ 3n
n = 0               0 _≤ 0
n = 1               2 ≤ 3
n = 3               6 ≤ 9
n = 100    200  ≤  300                     

n₀ = 0
C = 3 

Notasi ꭥ

t(n)  C ꭥ (g(n))
t(n) ≥ ꭥ (g(n))
2n ≥ n
n = 0               0 _≥ 0
n = 1               2 ≥ 1
n = 5               10 ≥ 5
n = 100    200  ≥  100                     

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 ≤ 2n
C₂ = 1
n₀ = 0

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

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

Tavg    = (2n + 2n)/2
            = 2n

            ≈ n

Notasi O 

t(n)  CO(g(n))
t(n) ≤ O(g(n))
2n ≤ 3n
n = 0               0 _≤ 0
n = 1               2 ≤ 3
n = 3               6 ≤ 9
n = 100    200  ≤  300                     

n₀ = 0
C = 3 

Notasi ꭥ

t(n)  C ꭥ (g(n))
t(n) ≥ ꭥ (g(n))
2n ≥ n
n = 0               0 _≥ 0
n = 1               2 ≥ 1
n = 5               10 ≥ 5
n = 100    200  ≥  100                     

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 ≤ 2n
C₂ = 1
n₀ = 0

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

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