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


[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.

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)


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

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




[url removed, login to view]





[url removed, login to view]





[url removed, login to view]





[url removed, login to view]





[url removed, login to view]





[url removed, login to view]


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

Ver mais: table tends, ppt architecture, make graph chart, infinity resources, html tabular, graph points make picture, find ppt, bound table, big time, line graph excel, make line graph, omega, maple, bit labs, excel add strings, maple lab, excel file data points, compile pdf, ppt pdf php, excel utility, performance graph, graph values time, function look table php, excel copy values, compile execute

Acerca do Empregador:
( 0 comentários ) United States

ID do Projeto: #6805505

1 freelancer está ofertando em média $25 para este trabalho


Hello, I am a Joomla developer plus graphic designer working from 3 years. Ready to build a professional and responsive website, please reply me quick i am ready to start work now.

$25 USD in 3 dias
(0 Comentários)