Java: counting operations to see growth rates
Analysis of algorithms asks how the work grows as the input size n grows. Timing a program mixes in the machine, the JVM warm-up, and the garbage collector, so a clean way to see growth is to count the basic steps directly.
Java
class Main {
static long[] count(int n) {
long linear = 0, quadratic = 0, logarithmic = 0;
for (int i = 0; i < n; i++) {
linear++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
quadratic++;
}
}
for (int k = n; k > 1; k /= 2) {
logarithmic++;
}
return new long[] {linear, quadratic, logarithmic};
}
public static void main(String[] args) {
for (int n : new int[] {8, 16, 32}) {
long[] c = count(n);
System.out.println("n=" + n + " linear=" + c[0] + " quadratic=" + c[1] + " log=" + c[2]);
}
}
}