Computer Science 210
Data Structures
Fall 2018, Siena College
EfficiencyClasses BlueJ Project
Click here to download a BlueJ project for EfficiencyClasses.
EfficiencyClasses Source Code
The Java source code for EfficiencyClasses is below. Click on a file name to download it.
/**
Print a table of typical relative running times as problem size
increases for problems with various complexities.
@author Jim Teresco, terescoj@cs.williams.edu, jteresco@siena.edu,
terescoj@strose.edu
*/
public class RunTimes {
public static void main(String[] args) {
java.text.DecimalFormat dfm = new java.text.DecimalFormat("##.###");
java.util.Scanner r = new java.util.Scanner(System.in);
System.out.println("If a problem of size n takes time t, how long does a larger problem take?");
while (true) {
System.out.println("Enter the multiplier of the problem size:");
long multiplier = r.nextLong();
if (multiplier == 0) break;
System.out.println("O(1)\t\tt\t\t2");
System.out.println("O(log n)\t"+dfm.format(Math.log(multiplier)/Math.log(2))+"t\t\t"+dfm.format(2*Math.log(multiplier)/Math.log(2)));
System.out.println("O(n)\t\t"+multiplier+"t\t\t"+2*multiplier);
System.out.println("O(n log n)\t"+dfm.format(multiplier*Math.log(multiplier)/Math.log(2))+"t\t\t"+dfm.format(2*multiplier*Math.log(multiplier)/Math.log(2)));
System.out.println("O(n^2)\t\t"+multiplier*multiplier+"t\t"+2*multiplier*multiplier);
System.out.println("O(n^3)\t\t"+multiplier*multiplier*multiplier+"t\t"+2*multiplier*multiplier*multiplier);
System.out.println("O(2^n)\t\t~t^{"+multiplier+"}\t"+Math.pow(2,multiplier));
}
}
}
/**
Print a table of typical relative problem size
increases for problems with various complexities.
@author Jim Teresco, terescoj@cs.williams.edu, jteresco@siena.edu,
terescoj@strose.edu
*/
public class ProblemSizes {
public static void main(String[] args) {
java.text.DecimalFormat dfm = new java.text.DecimalFormat("##.###");
java.util.Scanner r = new java.util.Scanner(System.in);
System.out.println("If a problem of size k takes a given amount of time, how large a problem can be");
System.out.println("solved in some multiple of that time (or on a computer that many times faster?");
while (true) {
System.out.println("Enter the multiplier of the computing time:");
long multiplier = r.nextLong();
if (multiplier == 0) break;
System.out.println("O(log n)\tk^{"+multiplier+"}");
System.out.println("O(n)\t\t"+multiplier+"k");
System.out.println("O(n log n)\t<"+multiplier+"k");
System.out.println("O(n^2)\t\t"+dfm.format(Math.sqrt(multiplier))+"k");
System.out.println("O(n^3)\t\t"+dfm.format(Math.pow(multiplier,1.0/3.0))+"k");
System.out.println("O(2^n)\t\t~k+"+dfm.format(Math.log(multiplier)/Math.log(2)));
}
}
}