CSE 321 Homework 20

Definition: Let f: integer^≥0 --> integer^≥0. Then, O(f) = {t: integer^≥0 --> integer^≥0 where there are constants c > 0 and m ≥ 0 such that t(n) ≤ c * f(n) for all n ≥ m}. When t is in O(f), we say t is O(f).

1. Using the definition of O( ), prove: 9×n² + 6×n + 3 is in O(n²).

2. Using the definition of O( ), prove: 5×n×log₂(n) + 4×n + 3×log₂(n) + 2 is in O(n×log₂n).

3. In the following code segment, assume that s and t are of type Array_Of_Integer with lower bounds of 1 and with upper bounds of n, where n is an integer greater than 1. Use O( ) notation to express the performance of the code segment as a function of n. [Assume all array operations are implemented in constant time.]

   {
       s[1] = t[1];
       pos = 2;
       while (pos <= t.Upper_Bound ())
       {
           s[pos] = s[pos-1] * t[pos] - 1;
           pos++;
       };
   }