SUNY Geneseo Department of Computer Science

Introduction to Asymptotic Notation

{Date}

CSci 240, Spring 2007
Prof. Doug Baldwin

Misc

Lab 4 (debugging) due tomorrow

Faculty applicant (Suprakash Datta) interviewing today

Sections 9.2.1 and 9.2.2

Run times for different algorithms, e.g., selection sort, initialization, search, something else
- n² vs n
Asymptotic notation (theta) to talk about proportionality of algorithms
Definition of f(n) = Θ( b(n) )
- f(n) ≤ c1 b(n) for all n ≥ n1
- f(n) ≥ c2 b(n) for all n ≥ n2
Informal definition of f(n) = Θ( b(n) )
- f(n) roughly proportional to b(n) for large n
Important thing about about a theoretical count is fastest growing term, asymptotic notation abstracts this out

Example: Find and prove simple asymptotic equivalents for...

(n² + n) / 2
- = Θ( n² )
- Proof:
  - (n² + n) / 2 ≤ c1 n² for n ≥ n1
    - c1 = 2, n1 = 1
  - (n² + n) / 2 ≥ c2 n² for n ≥ n2
    - c2 = 0.2, n2 = 1
    - or n²/2 + n/2 ≥ c2 n² , c2 = 1/2, n2 = 0
3 2ⁿ
- Look at what happens if you get the asymptotic form wrong: "oh, this is like n²", i.e., 3 2ⁿ = Θ(n²)
- Check aka prove
  - 3 2ⁿ ≤ c1 n² for n ≥ n1

[n^2 Seems to Overtake 2^n at n=2]

n1 = 2, c1 = 3?
- Counter-example! n = 5: 3 2⁵ = 96; 3 5² = 75
Maybe c1 and n1 don't exist
- Prove this by thinking about limits?
- Look at limit of ratio 3 2ⁿ / n² ≤ c1
- This limit is infinite, i.e., c1 has to be infinite

Two other forms of asymptoptic notation, Big-O and Big-Ω

Analyzing empirical data for consistency with an asymptotic hypothesis