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.


RunTimes.java

/**
   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));
	}
    }
}

ProblemSizes.java

/**
   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)));
	}
    }
}