Big-O Notation

// Demo Big-O Notation: implementasi dan pengukuran berbagai kelas kompleksitas.

// O(1) - konstan: akses elemen array by index
fun aksesKonstan(arr: IntArray, index: Int): Int = arr[index]

// O(log n) - logaritmik: binary search
fun binarySearch(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.lastIndex
    while (low <= high) {
        val mid = (low + high) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> low = mid + 1
            else -> high = mid - 1
        }
    }
    return -1
}

// O(n) - linier: jumlah elemen
fun jumlahkan(arr: IntArray): Int {
    var total = 0
    for (x in arr) total += x
    return total
}

// O(n log n) - linieritmik: merge sort (count operasi)
var hitungMerge = 0
fun mergeSort(arr: IntArray, left: Int = 0, right: Int = arr.lastIndex) {
    if (left >= right) return
    val mid = (left + right) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    val temp = IntArray(right - left + 1)
    var i = left
    var j = mid + 1
    var k = 0
    while (i <= mid && j <= right) {
        hitungMerge++
        if (arr[i] <= arr[j]) temp[k++] = arr[i++]
        else temp[k++] = arr[j++]
    }
    while (i <= mid) { temp[k++] = arr[i++]; hitungMerge++ }
    while (j <= right) { temp[k++] = arr[j++]; hitungMerge++ }
    for (x in temp.indices) arr[left + x] = temp[x]
}

// O(n^2) - kuadratik: bubble sort
var hitungBubble = 0
fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            hitungBubble++
            if (arr[j] > arr[j + 1]) {
                val t = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = t
            }
        }
    }
}

// O(2^n) - eksponensial: Fibonacci rekursif
var hitungFib = 0
fun fibNaif(n: Int): Int {
    hitungFib++
    return if (n <= 1) n else fibNaif(n - 1) + fibNaif(n - 2)
}

fun main() {
    println("=== Demo Big-O Notation ===")

    val dataSorted = intArrayOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
    println("Array: ${dataSorted.toList()}")
    println("O(1) akses index 5: ${aksesKonstan(dataSorted, 5)}")

    val idx = binarySearch(dataSorted, 23)
    println("O(log n) binary search 23 -> index $idx")

    println("O(n) jumlah elemen: ${jumlahkan(dataSorted)}")

    println()
    println("--- Perbandingan jumlah operasi ---")
    println("%-10s %-10s %-12s %-12s %-12s".format("n", "O(log n)", "O(n)", "O(n log n)", "O(n^2)"))

    val ukuran = listOf(10, 50, 100, 500)
    for (n in ukuran) {
        val log = jumlahOperasiLogN(n)
        val lin = n
        val nLogN = (n * log)
        val kuad = n * n
        println("%-10d %-10d %-12d %-12d %-12d".format(n, log, lin, nLogN, kuad))
    }

    println()
    println("--- Fibonacci eksponensial O(2^n) ---")
    for (n in listOf(5, 10, 15, 20, 25)) {
        hitungFib = 0
        val hasil = fibNaif(n)
        println("fib($n) = $hasil, pemanggilan: $hitungFib")
    }
}

fun jumlahOperasiLogN(n: Int): Int {
    var hitung = 0
    var i = n
    while (i > 1) { i /= 2; hitung++ }
    return hitung
}

=== Demo Big-O Notation ===
Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
O(1) akses index 5: 23
O(log n) binary search 23 -> index 5
O(n) jumlah elemen: 323

--- Perbandingan jumlah operasi ---
n          O(log n)   O(n)         O(n log n)   O(n^2)      
10         3          10           30           100         
50         5          50           250          2500        
100        6          100          600          10000       
500        8          500          4000         250000      

--- Fibonacci eksponensial O(2^n) ---
fib(5) = 5, pemanggilan: 15
fib(10) = 55, pemanggilan: 177
fib(15) = 610, pemanggilan: 1973
fib(20) = 6765, pemanggilan: 21891
fib(25) = 75025, pemanggilan: 242785