Problem 1. Use the definition of ”big-O” notation to show that 2×3 + 5×2 + 4x + 1 is O(x3).
Problem 2. Bring the following functions in the increasing order according to their growth rate: n3 + 88n2 + 3, log n4, 3n, n2 log n, n2n, 10000.
1
Problem 3. (a) Describe an algorithm that takes as input an integer n and computes n!
(b) Find the running time function T (n) of this algorithm.
2