CS2303 Tutorial 1 Exercises
1. You are given 30 integers as the input. Write a C++ program to output the largest value and the smallest integer value.
suppose a[0] to a[29] are storing these integers.
Method1:
Fix one integer, compare it with all the other integers. If it is smaller than all, then it is the smallest value; if it is larger than all, then it is the largest value. Do the above steps for all the integers.
Running time: roughly n2
Method2:
Set two references min and max, make them equal to a[0] at the beginning. For all the following integers a[1] to a[29], compare it with the current min and max, update min and max accordingly.
Running time: roughly 2n
Method3:
Do pairs of comparisons to decide which half of numbers will produce the largest value and which half of the numbers will produce the smallest value.
Running time: roughly 1.5n
Suppose your program for exercise 1 takes 0.5s if the input is 30 integers. How long will it take for 1000 integers if the running time is the following function:
T(n)=n (linear)
T(n)=100n2 (quadratic)
T(n)=2n3 (cubic)
T(n)=2n
Solutions for b will be provided in detail while the other problems are left for your exercises.
b. T(n)=100n2
30 integers will cause 100*302 basic steps, which maps to 0.5s
1000 integers will cause 100*10002 basic steps, which maps to ? s
We know that the running time is proportional to “number of basic steps”, therefore,
100*302/0.5=100*10002/?
? is roughly equal to 500
Different running time functions have different growing tendency when the input size grows. Among the programs which produce the same results, the ones which grows slowly will be the favorable program we choose