1. Pengantar Kompleksitas Algoritma

Dalam pemrograman, sebuah algoritma tidak hanya dinilai dari apakah algoritma tersebut menghasilkan jawaban yang benar, tetapi juga dari seberapa efisien algoritma tersebut.

Dua hal yang umum dianalisis:

1. Time Complexity → seberapa banyak operasi yang dilakukan algoritma.
2. Space Complexity → seberapa banyak memori tambahan yang digunakan.

Untuk menganalisis pertumbuhan waktu eksekusi terhadap ukuran data, kita menggunakan Big O Notation.

Contoh:

O(1)
O(log n)
O(n)
O(n log n)
O(n²)

Pada materi ini kita fokus pada:

• O(1) — Constant Time
• O(n) — Linear Time

O(1)

2. Apa Itu O(1)?

O(1) disebut Constant Time atau waktu konstan.

Artinya, jumlah operasi yang dilakukan algoritma tidak bergantung pada jumlah data (n).

Misalnya kita memiliki:

data = [10, 20, 30, 40, 50]

Kemudian kita ingin mengambil data pertama:

print(data[0])

Walaupun jumlah data berubah menjadi:

5 data
100 data
10.000 data
1.000.000 data

perintah:

data[0]

tetap hanya mengambil satu posisi tertentu.

Jadi kompleksitasnya:

O(1)

---

3. Contoh Sederhana O(1)

Contoh 1 — Mengakses Array

data = [10, 20, 30, 40, 50]

print(data[2])

Hasil:

30

Kita langsung menuju indeks 2.

Tidak perlu memeriksa:

10
20
30

satu per satu.

Kompleksitas:

O(1)

---

4. Contoh O(1) Menggunakan Variabel

nama = "Sutrisno"

print(nama)

Operasinya hanya mengambil nilai sebuah variabel.

Kompleksitas:

O(1)

---

5. Contoh Perhitungan O(1)

Misalnya:

a = 10
b = 20

hasil = a + b

print(hasil)

Operasi utamanya:

a + b

hanya dilakukan satu kali.

Tidak peduli apakah kita mempunyai data sebanyak:

n = 10
n = 100
n = 1.000
n = 1.000.000

operasi penjumlahan tersebut tetap satu kali.

Maka:

T(n) = 1

Sehingga:

O(1)

---

6. Ciri-Ciri O(1)

Algoritma biasanya termasuk O(1) apabila:

• Tidak menggunakan perulangan berdasarkan jumlah data.
• Mengakses data berdasarkan indeks tertentu.
• Mengambil nilai variabel.
• Melakukan operasi matematika sederhana.
• Jumlah operasinya tetap.

Contoh:

x = 10
y = 20

hasil = x * y

Kompleksitas:

O(1)

---

7. Apa Itu O(n)?

O(n) disebut Linear Time atau waktu linear.

Artinya, jumlah operasi algoritma bertambah sebanding dengan jumlah data.

Jika jumlah data bertambah 2 kali, secara sederhana jumlah pekerjaan algoritma juga bertambah sekitar 2 kali.

Contoh:

data = [10, 20, 30, 40, 50]

for angka in data:
    print(angka)

Program harus membaca setiap elemen.

Jika ada 5 data:

10
20
30
40
50

maka terdapat sekitar 5 operasi.

Jika terdapat 100 data, sekitar 100 operasi.

Jika terdapat 1.000 data, sekitar 1.000 operasi.

Maka:

O(n)

---

8. Contoh O(n) dengan Perulangan

data = [10, 20, 30, 40, 50]

for angka in data:
    print(angka)

Perulangan berjalan sebanyak jumlah elemen.

Jika:

n = 5

maka:

5 kali

Jika:

n = 100

maka:

100 kali

Jika:

n = 1.000

maka:

1.000 kali

Sehingga:

T(n) = n

dan:

O(n)

---

9. Contoh Mencari Data

Misalnya kita ingin mencari angka 50.

data = [10, 20, 30, 40, 50]

target = 50

for angka in data:
    if angka == target:
        print("Data ditemukan")
        break

Algoritma memeriksa data satu per satu:

10 → bukan
20 → bukan
30 → bukan
40 → bukan
50 → ditemukan

Pada kondisi terburuk, data yang dicari berada di bagian paling akhir.

Karena itu kompleksitasnya:

O(n)

---

10. O(1) vs O(n)

Perhatikan dua kode berikut.

Algoritma A

data = [10, 20, 30, 40, 50]

print(data[0])

Kompleksitas:

O(1)

Karena hanya mengambil satu posisi.

Algoritma B

data = [10, 20, 30, 40, 50]

for angka in data:
    print(angka)

Kompleksitas:

O(n)

Karena seluruh data diproses.

---

11. Perbandingan Jumlah Operasi

Misalnya jumlah data adalah:

n	O(1)	O(n)
1	1	1
10	1	10
100	1	100
1.000	1	1.000
10.000	1	10.000
100.000	1	100.000
1.000.000	1	1.000.000

Terlihat bahwa:

O(1) tetap konstan.

Sedangkan:

O(n) terus bertambah mengikuti jumlah data.

---

12. Analogi Kehidupan Sehari-hari

O(1)

Bayangkan ada 1.000 buku di rak.

Kita diminta mengambil:

Buku nomor 500.

Jika buku tersusun berdasarkan nomor dan kita langsung menuju posisi tersebut, kita tidak perlu memeriksa buku 1 sampai 499.

Ini menggambarkan:

O(1)

---

O(n)

Sekarang bayangkan 1.000 buku tersebut tidak memiliki urutan.

Kita diminta mencari:

Buku berjudul “Algoritma Pemrograman”.

Kita harus memeriksa:

Buku 1
Buku 2
Buku 3
...
Buku 1000

Dalam kondisi terburuk, kita memeriksa semuanya.

Ini menggambarkan:

O(n)

---

13. Contoh O(n) dengan Python

Menjumlahkan seluruh data

data = [10, 20, 30, 40, 50]

total = 0

for angka in data:
    total += angka

print("Total =", total)

Misalnya:

10 + 20 + 30 + 40 + 50

Setiap elemen diproses.

Jika jumlah data adalah n, maka perulangan berjalan n kali.

Kompleksitas:

O(n)

---

14. Contoh O(n) dengan JavaScript

<script>

let data = [10, 20, 30, 40, 50];

for (let i = 0; i < data.length; i++) {
    console.log(data[i]);
}

</script>

Perulangan:

i < data.length

menunjukkan bahwa jumlah iterasi bergantung pada jumlah data.

Maka:

O(n)

---

15. Bagaimana Menentukan O(1) atau O(n)?

Gunakan pertanyaan sederhana:

Pertanyaan 1

Apakah algoritma melakukan pekerjaan yang jumlahnya tetap?

Jika iya:

O(1)

Contoh:

print(data[5])

---

Pertanyaan 2

Apakah algoritma harus memproses setiap data?

Jika iya:

O(n)

Contoh:

for data in daftar:
    print(data)

---

16. Contoh Analisis Kode

Perhatikan:

def hitung(a, b):
    hasil = a + b
    return hasil

Tidak ada perulangan.

Jumlah operasi relatif tetap.

Maka:

O(1)

---

Sekarang:

def cetak_data(data):
    for item in data:
        print(item)

Perulangan bergantung pada jumlah elemen.

Jika:

n = jumlah data

maka:

T(n) = n

Jadi:

O(n)

---

17. Contoh Gabungan

Perhatikan:

data = [10, 20, 30, 40, 50]

print(data[0])

for angka in data:
    print(angka)

Ada:

print(data[0]) → O(1)

dan:

for → O(n)

Sehingga:

O(1) + O(n)

Dalam Big O, kita mengambil pertumbuhan terbesar:

O(n)

Karena:

O(1) + O(n) = O(n)

---

18. Kesimpulan

O(1) — Constant Time

Jumlah operasi relatif tetap

Contoh:

data[0]

Tidak peduli jumlah data:

10
100
1.000
1.000.000

akses tersebut tetap konstan.

---

O(n) — Linear Time

Jumlah operasi mengikuti jumlah data

Contoh:

for item in data:
    print(item)

Jika data bertambah, jumlah operasi juga bertambah.

---

Ringkasan

Kompleksitas	Nama	Karakteristik	Contoh
O(1)	Constant	Operasi tetap	data[0]
O(n)	Linear	Operasi mengikuti jumlah data	for item in data

Inti yang harus dipahami:

O(1) tidak berarti “1 detik”, tetapi pertumbuhan jumlah operasi tidak bergantung pada ukuran input.

O(n) tidak berarti “n detik”, tetapi jumlah pekerjaan tumbuh secara linear terhadap ukuran input.