P2: Analysis of algorithms

This session is about finding the asymptotic cost (i.e. running time) of simple algorithms as a function of the input size.

The theoretical tools we use are:

• notable sums from the problem class P1 (Exercise 1.1)
• Asymptotic notation
• Analysis of Iterative Algorithms (look at your theory slides, for instance)
• Master Theorem(s)
• Sorting algorithms

We continue with some problems from the EDA ProblemSet, section 1 Analysis of algorithms.

After class

To test your understanding, try exercises from the Collection of Solved Exams. For instance:

• 06/11/2020 Midterm EDA Exam Problem 2.a and 2.b
• 15/04/2021 Midterm EDA Exam Problem 1.b and 1.c
• 03/11/2022 Midterm EDA Exam Problem 2.a
• 02/11/2023 Midterm EDA Exam Problem 2
• 07/06/2021 Final EDA Exam Problem 1.c

The solutions of the above problems are in the same pdf containing their statement.