Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

Agenda

- Announcements
- Lecture 4 assignment recap
- Problem Set 2: Asymptotic Analysis [HTML] [PDF] continues, now due next Wednesday
- Asymptotic Analysis
- using limits

- Analyzing non-recursive algorithms

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