Menghitung T(n) Pseudocode Rekursif

Program Menghitung Min Max

Procedure MinMaks(input n = TabelInt,I,j:integer, output min, maks: integer)

{I.S. : }

{F.S. : }

Kamus :

min1, min2, maks1, maks2 :integer

Algoritma :

if (i = j) then

  min ← ni

  maks←ni

  else

   if(i=j-1) then

    min←ni

    maks←ni

    else

     maks←ni

     min←ni

   endif

else

k←(i+j) div 2

MinMaks(n, i, k, min1, maks1)

MinMaks(n, i, k+1, j, min2, maks2)

If(min1<min2)then

  min←min1

  else

min←min2

endif

if (maks<maks2)then

maks←maks2

else

maks←maks2

endif

Mencari T(n)

Relasi rekurrens :

                0                         ,n=1

T(n) =      1                          ,n=2

                2T(n/2)+2            ,n>2

T(n)        = 2T(n/2) + 2

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

T(n)        = 4(2T(n/8)+2)+4+2=8T(n/8) +8 +4+2

T(n)        =…..

T(n)        =2^k-1 T(2)+∑_i=1^k-12ⁱ

T(n)        =2^{k-1 .} . 1+2^k-2

T(n)        = 2(²log n )^-1+2(² log n)-2

T(n)        = n/2 + n-2

T(n)        =3n/2 – 2

T(n)        = 3n/2-2

Jadi T(n) € O(n)