Introduction to Data Structures
Running Time Analysis
The Lab1.java included with this assignment has two algorithms.
- Give as accurate (Big-Oh) an analysis as you can of the expected running time of each algorithm.
- Calculate the actual running time for each algorithm by writing (separate) programs to execute each algorithm 10 times, to get a good average. The program should print out the running time to the screen.
- Plot the average running time for both algorithms. Each algorithm should run ten times. The average of these ten runs should be plotted.
- Compare your analysis with the actual running times.
N is the size of input. Calculate the running time of each algorithm for N = 250, 500, 1000, 10000 and 20000
The input is a set of random integer numbers in range of [-9, 9].
Compare the running time of two algorithms. Plot the results and write your conclusion about the running time comparison of these algorithms.
Submission:
Submit the plot, conclusion and source code assignment under Running Time Analysis.
Note 1: compile your file .java and run the program before submitting it.
Note 2: How to locate Java file?
First you need to locate your java file.
- Right click on your project in Eclipse
- Click on “Properties”
- You can see the location of your Java file
Or
- Right click on your Java file in Eclipse.
- Copy the file
- Paste the file on your desktop
Note 3: Your Java program should follow the Style Guidelines. Style Guidelines document can be found in blackboard.
Guideline:
Program should begin with a header comment that provides the name of the homework, the name of the author, the date, and a short description of the program.
