SUNY Geneseo Department of Computer Science
Asymptotic
Notation
{Date}
CSci 141, Fall 2004
Prof. Doug Baldwin
Return
to List of Lectures
Previous Lecture
Misc
Return tests
Hand out Homework 1
- Working with files in Java
- Files, streams, and readers
![[Input Goes from File to Stream to Reader to Program]](javainput.gif)
- Exceptions
- Signal that something unusual happened
- Emergency exit from code that detects
unusual situation
Questions?
Reading Summary
Section 9.2
Relating step counts to execution time
Asymptotic notation
- Theta
- Θ(f(n)) means "roughly proportional to f(n)"
- Concerned with function when n is large
Ways to test asymptotic hypotheses
How to come up with asymptotic forms?
- Highest-order, fastest-growing, term
- e.g., 3n2 - n +9
| n |
3n2 - n + 9 |
n2 |
B / n2 |
| 1 |
11 |
1 |
11 |
| 2 |
19 |
4 |
4.75 |
| 5 |
79 |
25 |
3.16 |
| 10 |
299 |
100 |
2.99 |
| 20 |
1189 |
400 |
2.9725 |
| 50 |
7459 |
2500 |
2.9836 |
| 100 |
29909 |
10000 |
2.9909 |
| 200 |
119809 |
40000 |
2.995225 |
| 500 |
749509 |
250000 |
2.998036 |
- 3n2 - n + 9 = Θ(n2)
- Because highest-order term
is 3n2, and 3 is just constant
of proportionality
- Rule of thumb:
- Find highest-order term
- Discard constant coefficient
- Polynomials: highest-order term has
highest exponent
- 2n grows faster than any polynomial
- e.g., 2n + 100n5 + n2 - 3 = Θ(2n)
- More realistically, towers of Hanoi
on n disks takes 2n - 1 "move" operations
- So Towers takes Θ(2n) time
Next
Lists
Read Sections 11.1 through 11.3
Next Lecture