# Performance Lab

TODO: Make more, fatter, data points

Okay, just follow along, questions will be denoted with a Q.

Make some appropriate subdirectory for this lab and go there

Copy ~kschmidt/public_html/CS265/Labs/Performance to your lab directory

Resources

[url removed, login to view] and [url removed, login to view] - a quick lecture on Big-O (a upper bound, not necessarily tight)

[url removed, login to view] and [url removed, login to view] - solving recurrence relations

[url removed, login to view] - an example of dividing T(n) by f(n) to discover f(n) (using Maple)

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.

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)

E.g.:

n T(n) T(n) / f(n)

f(n) = n f(n)=n3 f(n)=n2

10

520

52

5.2

20

2080

104

5.2

30

4680

156

5.2

40

8320

208

5.2

50

13000

260

5.2

60

18720

312

5.2

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

to be continued see picture attached..

Habilidades: PHP, Arquitetura de software, Teste de Software