Given the following code give a theoretical analysis of the run time of your pro
ID: 3745418 • Letter: G
Question
Given the following code give a theoretical analysis of the run time of your program, based upon the recursive formula used:
public class Prog3 {
// Default input file path.
private static final String DEFAULT_INPUT_FILE_PATH = "input.txt";
//a matrix consisting of canoe prices at a given point
private static int[][]canoePrices;
//the cost of the trip at a given point
private static int[][]costMatrix;
//the best route, based on price, for a certain point
private static String[][]routeMatrix;
/**************************************************************/
/* Method: main */
/* Purpose: Runs the program */
/* Parameters: */
/* String [] args: arguments passed via the argument line */
/* Returns: Void */
/**************************************************************/
public static void main(String[] args) {
// Output file path from args or a default file location
final File inputFilePath = new File(
args.length > 0 ? args[0] : DEFAULT_INPUT_FILE_PATH);
matrixCreator(inputFilePath);
priceCalculator();
System.out.println("The minimum cost for the trip is $"
+costMatrix[0][costMatrix[0].length-1]);
System.out.println("The cheapest route for the trip is "+
routeMatrix[0][routeMatrix[0].length-1]);
System.out.println("The cheapest prices for each point are ");
matrixPrinter(costMatrix);
}
/**************************************************************/
/* Method: matrixCreator */
/* Purpose: creates the three matrices, filling the canoePrice*/
/* and filling the diagonal of the other two */
/* Parameters: */
/* String file: the name of the file data is read */
/* from */
/* Returns: Void */
/**************************************************************/
public static void matrixCreator(File file) {
try {
Scanner fileReader = new Scanner(file);
//takes the first number in the file and uses it as the
//size for the matrices
int matrixSize = fileReader.nextInt();
canoePrices = new int[matrixSize][matrixSize];
costMatrix = new int[matrixSize][matrixSize];
routeMatrix = new String[matrixSize][matrixSize];
//line of the file
String fileLine ="";
//row of the matrix, used to match rows
//in the file with the matrix
int matrixRow = 0;
//clear out the remainder of the first line
fileReader.nextLine();
while(fileReader.hasNext()) {
fileLine = fileReader.nextLine();
fileLine = fileLine.trim();
//split the line apart by spaces
String[] amounts = fileLine.split(" ");
//Align the last element of the line with the last element of
//the current row of the matrix
for(int spot = 1; spot<=amounts.length;spot++) {
canoePrices[matrixRow][canoePrices[matrixRow].length-spot]
= Integer.parseInt(amounts [amounts.length-spot]);
}
//move to the next row of the matrix
matrixRow++;
}
fileReader.close();
} catch(IOException ex) {
System.exit(1);
}
//fill the diagonal of the remaining matrices with the appropriate
//values
for(int spot = 0; spot<canoePrices.length-1; spot++) {
costMatrix[spot][spot+1]=canoePrices[spot][spot+1];
}
for (int locat = 0; locat<canoePrices.length-1; locat++) {
routeMatrix [locat][locat+1] = locat+","+(locat+1);
}
}
/**************************************************************/
/* Method: priceCalculator */
/* Purpose: calculate prices for each stop */
/* Parameters: */
/* Returns: Void */
/**************************************************************/
public static void priceCalculator() {
//begin at the 2nd diagonal, first row
for (int diag = 2; diag<canoePrices.length; diag++) {
for (int vert = 0; vert<canoePrices.length-diag; vert++) {
int horiz = vert + diag;
//assign the initial value of the minimum price to be
//the price for that specific post
int minval = canoePrices[vert][horiz];
int tempCol = horiz;
String route = "";
//assign the route to that point to be the
//current row until a 0 is encountered
while (canoePrices[vert][tempCol] != 0) {
route = vert + ","+tempCol+" "+route;
tempCol--;
}
//compare the current minimum to the sum of the
//leftmost point of the row and the point directly below the
//current point. If it is less, assign to be the minimum value
//repeat until the leftmost point reaches the desired point
for (int dist = vert+1; dist < horiz; dist++ ) {
if(costMatrix[vert][dist]+costMatrix[dist][horiz]<minval){
minval=costMatrix[vert][dist]+costMatrix[dist][horiz];
route=routeMatrix[vert][dist]+" "
+routeMatrix[dist][horiz];
}
}
costMatrix[vert][horiz] = minval;
routeMatrix[vert][horiz] = route;
}
}
}
/**************************************************************/
/* Method: matrixPrinter */
/* Purpose: prints out a matrix */
/* Parameters: */
/* int [][] matrix: the matrix to print out */
/* Returns: Void */
/**************************************************************/
public static void matrixPrinter(int[][]matrix) {
//for each line of the matrix print out the value
//at that point, repeat with every row of the matrix
for(int spot = 0; spot<matrix.length; spot++) {
for(int walk = 0; walk<matrix[spot].length; walk++) {
System.out.print(matrix[spot][walk] + " ");
}
System.out.println("");
}
}
}
input.txt is as follows:
4
10 15 50
40 20
35
Explanation / Answer
The running time complexity of matrixCreator() is O(N * M) where N is the number of lines in the input file and M is the number of amounts as each line.
And, the running time complexity of matrixPrinter() is O(N * M) where N and M are the number of rows and columns in the cost matrix.
priceCalculator():
The priceCalculator() function uses three for loops as given below.
for (int diag = 2; diag<canoePrices.length; diag++) { -------------> LOOP 1
for (int vert = 0; vert<canoePrices.length-diag; vert++) { -------------> LOOP 2
int horiz = vert + diag;
for (int dist = vert+1; dist < horiz; dist++ ) { -------------> LOOP 3
if(costMatrix[vert][dist]+costMatrix[dist][horiz]<minval){ -------------> RECURSIVE FORMULA
minval=costMatrix[vert][dist]+costMatrix[dist][horiz];
route=routeMatrix[vert][dist]+" "
+routeMatrix[dist][horiz];
}
}
}
}
Clearly, if the number of rows in canonPrices[][] is N, then LOOP1 will run N times, LOOP2 will run N times (in worst case when diag = 0) and LOOP 3 will run N times (since horiz = vert + diag and vert = N - diag).
Therefore the recursive formula is called N*N*N times (in worst case). Hence, the running time complexity of priceCalculator() is O(N^3).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.