Question 1. Using the piece of code in Table # 1 below, Evaluate the time complexity of the 3 different algorithms to produce the sum of the first n numbers as indicated in Table # 2 below.
Question 2. Compare the result obtained for various value of n. You are to display the result in a comparative table and possibly plot a comparative graph (curve).
Table 1: Program Execution Time estimation
import java.util.Date
Date current = new Date();
long beginTime =
current.getTime();
myMethod(); //code to be timed
current = new Date();
long endTime = current.getTime();
long TotalExecutionTime = endTime - beginTime; long startTime = System.currentTimeMillis(); long endTime = System.currentTimeMillis();
// long startTime = System.nanoTime();
Table 2: Three Algorithms to implement the sum 1 to n
Algorithm A
Sum = 0
for i = 1 to n Sum = Sum + i
Algorithm B
Sum = 0
for i = 1 to n {
for j = 1 to i Sum = sum + 1 }
Algorithm C
Sum = n * ( n + 1 ) /2
3. Using the getTime() as shown above, display a table of the run time of each algorithm for the following values of n: 10, 100, thousand, ten thousands, hundred thousand, one million.
|
Algorithms
|
n=10
|
n=100
|
n=1000
|
n=10,000
|
N=100,000
|
|
Algorithm A
|
T=
|
|
|
|
|
|
|
|
|
|
|
|
|
Algorithm B
|
T=
|
|
|
|
|
|
Algorithm C
|
T=
|
|
|
|
|
|
|
|
|
|
|
|