Mencari T(n) dari Psedocode Percabangan Faktorial

Psedocode Percabangan Faktorial

Function Faktorial Input  N : integer) ← real

{I.S.  : harga N sudah terdefinisi}

{F.S. : menghasilkan fungsi faktorial}

Kamus:

    Fak   : real

    i      : integer

Algoritma:

    if   (N = 0) or (N = 1)  then

           Faktorial  ←  1

     else

           Fak  ←  1

           for  i  ←  2   to   N   do

                Fak  ← Fak  *  i  

           endfor

           Faktorial  ←  Fak

     Endif

EndFunction

Menghitung T(n)

N = n

Dalam (for - endfor) = T(Min) : n

                       T(Max) : n

Dalam (if - endif) = T(Min) : 1

                      T(Max) : 2

Operasi Dasar	Cop	C(n)
*         = 1 =         = 2    ←         = 4n+1	a b c	1na 2nb (4n+1)c

T(n) = Cop . C(n)

        = (1na) + (2nb) + (4n+1)c

T(avg) = 1na + 2nb + (4n+1)c  = n

                            n

MENCARI  NOTASI ASIMTOTIK
  O                                                       (Oh)

(Omega)

(Theta)

For-Endfor T(min) : n

Big O(Oh)

T(min) :  n    €    O(n)

          n    ≤    n

         _________________

         No : 0    C : 1

N = 0     n    ≤    0    √

N = 100   n    ≤    n    √

Big (Omega)

T(min) :  n    €    (n)

          n    ≥    n

          _________________

          No : 0     C : 1

N = 0     n    ≥    0    √

N = 100   n    ≥    n    √

Big (Theta)

T(min) :  n    €    (n)

          n   ≤    n    ≥    n

          _______________________

          No : 0           C : 1

Batas atas : O(n)

      

     T(n) : 1n    ≤    1n²    ≥    1n²

Batas bawah  (n)

     1n  = 1n

     C1 = 1, C2 = 1, No = n

For-Endfor T(max) : n

Big O(Oh)

T(min) :  n    €    O(n)

          n    ≤    n

         _________________

         No : 0    C : 1

N = 0     n    ≤    0    √

N = 100   n    ≤    n    √

Big (Omega)

T(min) :  n    €    (n)

          n    ≥    n

          _________________

          No : 0       C : 1

N = 0     n    ≤    0    √

N = 100   n    ≤    n    √

Big (Theta)

T(min) :  n    €    (n)

          n   ≤    n    ≥    n

          ______________________

          No : 0         C : 1

Batas atas : O(n)

      

     T(n) : 1n    ≤    1n²    ≥    1n²

Batas bawah  (n)

     1n  = 1n

     C1 = 1, C2 = 1, No = n

If-Endif T(min) : 1

Big O(Oh)

T(min) :  1    €    O(n)

          1    ≤    1n

          _________________

          No : 1   C : 1n

N = 0     1    ≤    0   x

N = 100   10   ≤    100  x

Big (Omega)

T(min) :  1    €    (n)

          1    ≥    1n

          _________________

          No : 1      C : 1n

N = 0     1    ≥    0    √

N = 100   1    ≥    100  x

Big (Theta)

T(min) :  1    €    (n)

          1   ≤    1n    ≥    1

          _______________________

          No : 0           C : 1n

Batas atas : O(n)

      

     T(n) : 1n    ≤    1n²    ≥    1n²

Batas bawah  (n)

     1n  = 1n²

     C1 = 1, C2 = 1, No = 1n²

If-Endif T(max) : 2

Big O(Oh)

T(Max) :  2    €    O(n²)

          2    ≤    1n²

          _________________

          No : 2   C : 1n²

N = 0     2    ≤    0   √

N = 100   10   ≤    100  x

Big (Omega)

T(Max) :  2    €    (n²)

          1    ≥    1n

          _________________

          No : 2      C : 1n²

N = 0     2    ≥    0    √

N = 100   2    ≥    100  x

Big (Theta)

T(Max) :  2    €    (n²)

          2    ≤    1n²    ≥    1

          _______________________

          No : 2          C : 1n²

Batas atas : O(n²)

      

     T(n) : 2n    ≤    2n²    ≥    1n²

Batas bawah  (n)

     2n  = 1n²

     C1 = 2, C2 = 1, No = 1n²

T(AVG): 1na + 2nb + (4n+1)c ~  n

            n           ~

Big O(Oh)

T(avg) :  : 1na + 2nb + (4n+1)c ~  n €    O(n²)

                   n          ~

                 

          : 1na + 2nb + (4n+1)c ~  n ≤    1n²

                  n            ~

    

          No : 1+2+4 = 7 C : 1

N = 0     7    ≤    0   x

N = 100   10   ≤    100  √

Big (Omega)

T(avg) :  7    €    (n²)

          7    ≥    1n

          _________________

          No : 7      C : 1

N = 0     7    ≥    0    √

N = 100   7    ≥    100  x

Big (Theta)

T(avg) :  7    €    (n²)

          7    ≤    1n²    ≥    1

          _______________________

          No : 7          C : 1

Batas atas : O(n²)

      

     T(n) : 7n(n-1)    ≤    7n²-7n    ≥    7n²

                  

Batas bawah  (n)

     7n  = 7n²

     C1 = 7, C2 = 7, No = 7n²