Complexity.java

public class Complexity {
    public static void main(String[] args) {
        int n = 100_000;
        int[] a = new int[n];

        java.util.Random r = new java.util.Random();

        for (int i = 0; i < n; ++i) {
            a[i] = r.nextInt();
        }

        System.out.println("n = " + n);

        long s, e;

        s = System.currentTimeMillis();

        int x1 = 0;

        for (int i = 0; i < n; ++i) {
            x1 += a[i];
        }

        e = System.currentTimeMillis();
        System.out.println("O(n) = " + (e - s) + " ms");

        int m = log2(n);

        s = System.currentTimeMillis();

        int x2 = 0;

        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < n; ++i) {
                x2 += a[i];
            }
        }

        e = System.currentTimeMillis();
        System.out.println("O(n * log(2, n)) = " + (e - s) + " ms");

        s = System.currentTimeMillis();

        int x3 = 0;

        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                x3 += a[i];
            }
        }

        e = System.currentTimeMillis();
        System.out.println("O(n * n) = " + (e - s) + " ms");

        System.out.println("X = " + Integer.toHexString(x1 + x2 + x3));
    }

    public static int log2(int n) {
        if (n <= 0) throw new IllegalArgumentException();
        return 31 - Integer.numberOfLeadingZeros(n);
    }
}

n = 100000
O(n) = 4 ms
O(n * log(2, n)) = 6 ms
O(n * n) = 3530 ms
X = 1fa29f4c