public class AnalisisBigO {

    public static void main(String[] args) {
        System.out.println("=== Loop bersarang: n naik 2x, operasi naik 4x ===");
        for (int n = 10; n <= 40; n *= 2) {
            System.out.printf("n=%3d -> %5d iterasi loop dalam%n",
                    n, hitungLoopBersarang(n));
        }

        System.out.println();
        System.out.println("=== Binary search: n naik 4x, perbandingan hanya +2 ===");
        for (int n = 1024; n <= 16384; n *= 4) {
            System.out.printf("n=%5d -> %2d perbandingan (target di ujung kanan)%n",
                    n, hitungBiner(n));
        }

        System.out.println();
        System.out.println("=== Suku rendah tenggelam: f(n) = 3n^2 + 20n + 7 ===");
        for (int n = 10; n <= 10000; n *= 10) {
            long fn = 3L * n * n + 20L * n + 7;
            System.out.printf("n=%5d -> f(n)=%10d, f(n)/n^2 = %.3f%n",
                    n, fn, (double) fn / (1L * n * n));
        }
    }

    static long hitungLoopBersarang(int n) {
        long iterasi = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                iterasi++;
            }
        }
        return iterasi;
    }

    static int hitungBiner(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = i + 1;
        }
        int target = n;          // nilai terbesar: kasus paling kanan
        int lo = 0;
        int hi = n - 1;
        int perbandingan = 0;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            perbandingan++;
            if (a[mid] == target) {
                return perbandingan;
            }
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return perbandingan;
    }
}