2.1 Prove by induction
Prove by induction that for all n greater than or equal to 1:
∑_(i=1)^n i 3=∑_(i=1)^n i
Hints:
• Start with n I as the base case and then the inductive step
• You already know what I + 2 + + n is for any n (discussed in class), and you should use this fact in your proof.
• You will also need to do a little bit of algebra manipulations
2.2. Function Growth Rates Order the following functions from slowest growth rate to fastest growth rate. If any of the functions grow at
the same rate, make sure to indicate this.
• n2
• n log (n)
• 2/n
• log2 (n)
• 2^
• sqrt (n)
• 86
• n2 log (n)
• n 1.5
c. TI(n) + T2(n) is 0(f(n))
d. TI(n) is O(T2(n))
2.4. Running Times (50 points total, 10 points for each program fragment) For each of the following program fragments, do the following:
a) Give an asymptotic analysis of the running time using big-O.
b) Implement the code in Java, and give the actual running times for several (at least five) values of n, to understand the running time as a function of n (e.g., is the running time linear in n).
c) Compare your analysis with the actual running time.
1. sum = 0;
for (i = 0; i < n; i++)
{
sum++;
}
2. sum = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
sum++;
}
}
3. SUM = 0;
for (i = 0; i < n; if+)
(
for (j = 0; j < j++)
SUM++;
a. SUM = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < n • n; 7++)
(
sum++;
5. sum e 0;
for (i e 0; i < n; i++)
(
for (j e 0; j < j++)
if (j t i - 0)
(
for (k e 0; k < j; k++)
sun++;
1 1
For part b), you will use large values of n to get meaningful experimental results. To get the tonal running time, I have written a class
Timelnterval, where the library functions are called. You may use the code below to get the actual running time of your program.
// Timelnterval. Java
Public class Timelnterval
{
private long startTime, endTime;
private long elapsedTime;
// Time Interval in milliseconds
public void startTiming()
{
elapsedTime = 0;
startTime = System.currentTimeMillis();
public void endTiming() endTime = System.currentTimeMillis();
elapsedTime = endTime - startTime;
// return the time in seconds between the start and the end public double getElapsedTime()
{
return (double) elapsedTime / 1000.0;
// in main method Timelnterval t = new Timelnterval();
t.startTiming(); // start the watch
// run your loop t.endTiming();
// stop the watch
// t.getElapsedTime()
returns the time interval in seconds System.out.println("Running time: " + t.getnapitedTime());