SUNY Geneseo Department of Computer Science

Asymptotic Notation, Part 2

Return to List of Lectures

Misc

Repairing the snow day

• Exam 1 next Friday (Feb. 23)
  • Covers material from start of semester through class before exam (e.g., pre- and post-conditions, recursion, induction, recurrences, experiments, etc.)
  • 4 - 6 short-answer questions, similar to problem set or lab questions
  • Full class period (50 minutes)
  • Open book, open notes, open computer (but closed-person)
• Do this week's lab next week

Faculty applicant (Alexander Dekhtyar) interviewing Monday

• Student roundtable 11:30 - 12:00, Fraser 208
• Research talk (data description for digitized manuscripts) 2:30, Milne 213
• Model class (XML data management, databases), 4:30, Welles 123

Questions?

Two Other Asymptotic Notations

Each concentrates on one half of the definition of Θ(...)

f(n) grows no faster than proportional to b(n)

• f(n) = O( b(n) )
• There exist constants c > 0 and n0 such that f(n) ≤ c b(n) for all n ≥ n0
• Sets upper bound on f(n)

f(n) grows no slower than proportional to b(n)

• f(n) = Ω( b(n) )
• There exist constants c > 0 and n0 such that f(n) ≥ c b(n) for all n ≥ n0
• Lower bound on f(n)

Examples

• 4n² - 2 = O( n² )
• 4n² - 2 = O( n³ )
• 4n² - 2 = Ω( n² )
• 4n² - 2 = Ω( n )

f(n) = Θ( b(n) ) if and only if f(n) = O( b(n) ) and f(n) = Ω( b(n) )

Empirical Application

How to tell if measured data are consistent with an asymptotic hypothesis

Section 9.2.3

• Mostly examples, what's important idea behind them?
• Hypothesis: dependent variable is Θ( f(n) ) for independent variable n
• Test by dividing measured dependent values by f(n), look for values between two constants as n gets big
• i.e., finding c1 and c2 from definition of Θ

Example

• The random names list
• Based on an algorithm that computes a "rank" for each student
• Rank depends on both how many times student has been called, n, and a random factor.
• Claim that ranks are actually Θ(n)
  • Looked at this in a spreadsheet based on the one for actual random names. Also considered ranks that were Θ(n²).

Next

A short-cut for finding asymptotic solutions to many recurrences