Algorithms and Data Structures (INF1, Autumn'05)
Lecture 3
Main topic: Complexity of algorithms.
Lecture Plan
- algorithms efficiency and analysis of algorithms
- time and space complexity
- worst-case and average-case complexity
- measuring the complexity of recursive and iterative algorithms
- solving recurrence equations (repeated substitutions)
- asymptotic complexity,
O-notation
Reading
- Chapter 2 of Algorithms and Data Structures:
Design, Correctness and Analysis by Jeffrey H. Kingston
[Note: Section on tree traversal can be safely skipped.]
- Discrete Mathematics and its Applications: 3.2 Introduction
to Mathematical Induction (available in the course folder).