Analisis algoritma

1.      2. Tn = 1/3 + 2/3 + 1 + 4/3 + …… + 1/3n

a.       Tentukan kompleksitas waktu

b.      Tentukan big O

Jawab :

       a). Tn = 1/3 + 2/3 + 1+ 4/3+………….+ 1/3 n

    Tn = 1/3 (1+2+3+4+………………….+ n)

    1/3. ½ n (n+1)

    1/6 n (n+1)

    1/6 n² + 1/6 n

    Tn = O (n²)

b). 1/6 n² + 1/6 n ≤ 1/6 n² + 1/6 n²

       1/6 n² + 1/6 n ≤ 1/3 n²

       C = 1/3 ,  n₀= 1 ,   n ≥ 1

===============================================================

1.      3. Terdapat persoalan berikut:

Terdapat sekumpulan array bertipe integer, kemudian tentukan total nilainya.

a.       Jelaskan operasi dasarnya

b.      Buat algoritmanya

c.       Tentukan kompleksitas waktu

Jawab:

        a). Menjumlahkan semua nilai dari masing- masing array

b). tot ← 0

     for i  ← 1 to n do

          tot  ← tot + A [i]    O(1)

     endfor

c). Tn = n . O(1)

          = O (n)