Questions (15 points):

1. For each of the following problems, propose the key action/operation you would use to determine the time complexity (short answers are fine here). What is the smallest time complexity of an efficient algorithm solving that problem.
   1. (3 points) Consider an nn matrice B(bij) where i and j vary from 1 to n . The problem is to compute the trace of Matrix B 1nbii i.e., adding the elements of the matrix diagonal.

Key action/operation is .......

smallest time complexity is ...........

2. (3 points) Consider a sequence A containing n real numbers. The problem is to find the number of occurrences of a real b in Sequence A.

Key action/operation is .......

smallest time complexity is ...........

3. (3 points) Given an integer n , and real numbers a and x compute i=0naxi

Key action/operation is .......

smallest time complexity is ..........

4. (3 points) Given an integer n , compute i=1ni (Product on the n first integers)

Key action/operation is .......

smallest time complexity is ..........

5. Given an integer n , convert and display n in base 11.

Key action/operation is .......

smallest time complexity is ..........