TUGAS 5

Analisis Algoritma Rekursif

1. Algorithm S(n)

   //Input: A positive integer n

   //Output: The sum of the first n cubes

   if n = 1 return 1

   else return S(n − 1) + n ∗ n ∗ n

 Operasi Dasar Utama : Perkalian

 M(n) = M(n − 1) + 2,  M(1) = 0

 

 Subtitusi :

 M(n) = M(n − 1) + 2

          = [M(n − 2) + 2] + 2 = M(n − 2) + 2 + 2

          = [M(n − 3) + 2]+2+2 = M(n − 3)+2+2 + 2

          = ...

          = M(n − i) + 2i

          = ...

          = M(1) + 2(n − 1) = 2(n − 1)

2. Algorithm Power(n)

   //Computes 2n recursively by the formula 2n = 2n−1 + 2n−1

   //Input: A nonnegative integer n

   //Output: Returns 2n

   if n = 0 return 1

   else return Power(n − 1) + Power(n − 1)

  Operasi Dasar Utama : Pengurangan

  A(n) = 2A(n − 1) + 1,  A(0) = 0.

 Subtitusi :

 A(n) = 2A(n − 1) + 1

         = 2[2A(n − 2) + 1] + 1 = 2^(2)A(n − 2) + 2+ 1

         = 2^(2)[2A(n − 3) + 1] + 2 + 1 = 2^(3)A(n − 3) + 2^(2) + 2+ 1

         = ...

         = 2^(i)A(n − i) + 2^(i−1) +2^(i−2) + ... + 1

         = ...

         = 2^(n)A(0) + 2^(n−1) + 2^(n−2) + ... + 1 = 2^(n−1) + 2^(n−2) + ... + 1 = 2n − 1.

3. Algorithm Min2 (A[l..r])

    if l= r return A[l]

    else temp1 ← Min2 (A[l.. (l + r)/2 ])

           temp2 ← Min2 (A[ (l + r)/2 +1..r])

          if temp1 ≤ temp2 return temp1

          else return temp2

  Operasi Dasar Utama : Pembagian

  C(n) = C( n/2 ) + C( n/2 ) + 1 untuk n > 1,  C(1) = 0

  n = 2^(k)

  Subsitusi :

  C(2^(k))  = 2C(2^(k−1)) + 1

                  = 2[2C(2^(k−2))+1]+1 = 2^(2)C(2^(k−2)) + 2 + 1

                  = 2^(2)[2C(2^(k−3)) + 1] + 2 + 1 = 2^(3)C(2^(k−3)) + 2^(2) + 2 + 1

                  = ...

                  = 2^(i)C(2^(k−i)) + 2^(i−1) +2^(i−2) + ... + 1

                  = ...

                  = 2^(k)C(2^(k−k)) + 2^(k−1) +2^(k−2) + ...+1 = 2^(k) −1 = n − 1