Using the time utility
We're going to use time to gather runtime data about our quicksort, on strings.
We will sort inputs of 10,000, 20,000, ... , 60,000 words, and graph our results.
Compile your sort:
gcc -o sort1 sort1.c quicksort.c
For each input file, [url removed, login to view], get the time to execute:
time sort1 < file > /dev/null
I would use the reported user time
We want to find an Theta equivalence class for T(n), our observed times:
Put your six points (n, T(n)) in a table
Graph your six points (use Excel, gnuplot, Maple)
Did the graph tend towards a (non-zero) constant?
We wish to find f(n), such that T(n) = Θ( f(n) )
Guess at f(n). E.g., start at f(n) = n
Add a column to you table, T(n)/f(n)
graph T(n)/f(n) vs n
Does function approach a non-zero constant?
If the graph tends toward zero, then f(n) is an upper bound, but not tight. T(n = ο( f(n) )
If the graph heads off to infinity, then f(n) is a lower bound, but not tight. T(n = ω( f(n) )
Zero in on f(n)
Clearly T(n) is increasing. So, it is bound below (but not tightly) by a constant. We say T(n) = ω( 1 ).
Note: Big-O is an upper bound, which may or may not be tight. Little-O is a loose upper bound, which is not tight. Similarly, Big-Omega is a lower bound, which may or may not be tight, and little-omega, ω, is a loose lower bound, not tight.
When we divide T(n) by f(n) = n, we see these values still increasing to ∞. So, T(n) is bound below by a line, but not tightly. We say T(n) = ω( n ). In other words, T(n) grows faster than a line.
So, we choose f(n) = n3, and we see that T(n)/n3 is probably decreasing to zero (we need to look around a bit more to be sure). This means that n3 is an upper bound, but not tight. I.e., T(n) grows more slowly than n3. T(n) = ο( n3 ).
We now choose f(n) = n2. Well, I should've made this example a little more interesting. We can surmise that T(n) is, in fact, 5.2 n2. The important point is that T(n) / n2 is tending towards some non-zero constant. So, T(n) = Θ( n2 ).
Q 1 Supply your chart (that is just tabular data, n, T(n), T(n)/f(n) for various choices of f(n)), not a graph, and your conclusions
Contact me for the whole page info you need to finish the test