ABSTRACT
This chapter revisits basic notions on the cost of an algorithm and on the complexity of a problem. To illustrate these notions, in Section 1.1, we study the problem of computing xn, given x and n (where n is a positive integer). Then, in Section 1.2, we recall the classical asymptotic notations O, o, Θ, and Ω. Finally, exercises are proposed in Section 1.3, with their solutions in Section 1.4.
