Nama : Riyan Sutantio Bangkit Nugroho

NIM : L200180180

Tugas E-Learning
Algoritma dan Struktur Data
Analisis Algoritma

1. Apa itu kompleksitas pada suatu algoritma?

Kompleksitas merupakan suatu tingkat kerumitan dalam algoritma untuk

menerangkan atau menjelaskan algoritma tersebut. Dan kompleksitas memiliki dua
macam jenis, yang pertama kompleksitas waktu ( seberapa banyak waktu yang
digunakan untuk menjalankan algoritma tertentu) dan kompleksitas ruang (seberapa
banyak ruang yang digunakan untuk menjalankan algoritma tertentu).

2. Jelaskan manfaat dalam melakukan analisis kompleksitas dari suatu algoritma!

Dengan menganalisis suatu kekompleksitasan sebuah algoritma maka dapat

mengidentifikasi satu algoritma yang paling efisien untuk digunakan.

3. Jelaskan tentang konsep Big-O Notation pada suatu algoritma; jelaskan cara
menentukan Big-O Notation pada suatu algoritma!

Big-O Notation adalah suatu cara untuk mengubah atau mengkonversi keseluruhan
langkah dari suatu algoritma kebentuk aljabar, dengan menhiraukan konstanta yang
lebih kecil dan koefisien yang tidak berdampak besar terhadap suatu
kekompleksitasan.

Cara menentukan Big-O Notation adalah dengan mengambil konstanta terbesar dalam
bentuk aljabar supaya dapat menentukan termasuk kedalam kompleksitas yang mana
dengan mengabaikan konstanta yang lebih kecil dan koefisien yang tidak berdampak.

4. Jelaskan tentang konsep best case, average case, dan worst case pada suatu algoritma!
a. Best case

Best case dalam konsep ini merupakan algoritma yang membutuhkan waktu
paling minimal.

b. Average case

Average case dalam konsep ini merupakan algoritma yang membutuhkan

waktu rata-rata.
 c. Worst case

Worst case dalam konsep ini merupakan algoritma yang membutuhkan waktu
paling maksimal.

5. Jelaskan bagaimana ukuran suatu input mempengaruhi running time dari suatu
algoritma!

Jika mengambil contoh dari penggunaan big o notation, contoh jika kita misalkan
input = n. maka, jika kita menggunakan O(1) yang artinya seberapa banyak data yang
dikasih tetap akan diselesaikan dengan wakti 1 detik. Jika O(N) yang artinya waktu
yang dibutuhkan untuk menyelesaikan data tersebut sebanding(berbanding lurus),
misal n=10 dapat diselesaikan dalam waktu 1 detik. Jika n=1000 dapat diselesaikan
dalam waktu 100 detik. Jika O(N 2) yang artinya waktu yang dibutuhkan untuk
menyelesaikan data tersebut berbanding kuadrat dengan input, misal n=10 dapat
diselesaikan dalam 1 detik, maka jika n=1000 harus diselesaikan dalam waktu
10.000detik.
hal tersebut membuktikan bahwa didalam kompleksitas algoritma banyak data dapat
mempengaruhi running time dalam menjalankan algoritma tertentu.

6. Berikan contoh algoritma yang memiliki kompleksitas:

a. O(1)
a=b
b=c
c=a
Kompleksitas O(1) merupakah algoritma kompleksitas yang memiliki hasil
yang konstan karena tidak ada perubahan didalamnya.

b. O(log n)
count = 0
i = 32
while i >= 1 :
count = count +1
i = i//2
Kompleksitas O(logn) merupakan algoritma kekompleksitasan yang memiliki
laju pertambahan waktunya lebih lambat dari pada pertumbuhan n.

c. O(n)
for i in range (0,n):
print i
Kompleksitas O(n) merupakan algoritma kekompleksitasan yang memiliki
laju pertambahan waktunya sebanding dengan nilai pertumbuhan n.
 d. O(nlogn)
for i in range (0,n):
count = 0
i = 32
while i >= 1 :
count = count +1
i = i//2
Kompleksitas O(n log n) merupakan algoritma kekompleksitasan yang
memiliki laju pertambahan yang hamper sama dengan O(logn) tetapi
kompleksitas ini tergantung pertumbuhan n yang bisa menyebabkan hasil dua
kali lebih besar dari O(logn).

e. O(n2)
for i in range(0,n):
for j in range(0,n):
print i*j
Kompleksitas O(n2) merupakan algoritma kekompleksitasan yang memiliki
laju pertambahan waktu yang kuadratik dari n. jadi ini lebih bagus untuk n
yang bernilai kecil.

f. O(n3)
for i in range(0,n):
for j in range(0,n):
for k in range(0,n):
print i*j*k
Kompleksitas O(n3) merupakan algoritma kekompleksiasan yang memiliki
laju pertumbuhan yang menaikkan n menjadi dua kali semula dan menaikkan
running time empat kali dari semula.

7. Jelaskan alasan anda mengapa suatu algoritma dengan kompleksitas O(log n) lebih
sederhana daripada O(n), dan O(n) lebih sederhana daripada O(n2)!

Mengapa O(n) lebih besar dari O(logn), jika n = 1 maka log n dari n adalah 0, jika n =
10 maka log n dari n adalah 1, jadi dapat disimpulkan bahwa O(n) lebih besar dari
O(logn). Dan juga karena algoritma O(logn) memecahkan persoalan besar dengan
mentransformasikan menjadi persoalan yang lebih kecil dengan ukuran yang sama.

Mengapa O(n) lebih sederhana dari O(n 2), karena pada O(n) menjadikan n menjadi 2n
dan waktunya juga akan berbanding sama dengan n. lalu untuk O(n 2) menjadikan n
menjadi 2n dan menjadikan waktu menjadi empat kali semula. Jadi dapat disimpulkan
bahwa O(n) lebih sederhana dari O(n2).