Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 5: Asymptotic Analysis; Analyzing Non-Recursive Algorithms
Date: Wednesday, January 28, 2015
Agenda
- Announcements
- Lecture 4 assignment recap
- Problem Set 2: Asymptotic Analysis [HTML] [PDF] continues, now due next Wednesday
- Asymptotic Analysis
- Analyzing non-recursive algorithms
Lecture 5 Assignment
Due at the start of class, Monday, February 2.
Please submit answers to these questions
in Submission
Box under "LA5" or in hard copy by the
start of our next class. We will discuss these questions at the
start of class, so no late submissions are accepted. Please be sure
that your name is clearly indicated in all submissions.
- Levitin Exercise 2.2.3, p. 59. For part (a), use the definition of
Big Θ.
For the others, you may use the definition or prove using limits.
(5 points)
- Levitin Exercise 2.2.5, p. 60 (3 points).
Terminology
- L'Hôpital's Rule
- Stirling's formula
Links