P1: Asymptotic notation

Welcome to the first EDA problem class!

This session is about exercises on the asymptotic growth of functions. Later in the course we will be interested in functions associated to algorithms (typically the running time and how it scales w.r.t. the input size), but for the moment they are just functions without any algorithm in mind.

The theoretical tools we use are:

• Induction
• Limits
• Basic properties of \log(n) and n!
• Asymptotic notation (O, \Omega and \Theta)

We consider the following 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 1.b
• 15/04/2021 Midterm EDA Exam Problem 1.a
• 03/11/2022 Midterm EDA Exam Problem 1.b
• 02/11/2023 Midterm EDA Exam Problem 1.b
• 07/06/2021 Final EDA Exam Problem 1.a

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