From the Text

Complete the following questions from the text:

• Section 3.1: 6, 24.
  • Describe in pseudocode.
• Section 3.2: 18, 24.
  • You're free to use the theorem in question 27 (without proving it) if you like.
• Section 3.3: 8.
  • Compare answer to question 7(b): \(2n\) multiplications and \(n\) additions.
• Section 3.4: 8, 12.

Questions

1. What is the big-Θ running time of this algorithm? Assume the input list has \(n\) elements.

   procedure print_things(list):
       end = length(list)
       while end > 1
           total = 0
           for i from 0 to end-1
               total += list[i]
           print total
           end -= 1

2. The following algorithm computes \(a^b\) for \(b\) a natural number:

   procedure power(a, b)
       result = 1
       for i from 1 to b:
           result *= a
       return result

   What is the (big-Θ) running time of this algorithm?

3. Prove from the definition that \(f(x)=x^3 + 12x\log x\) is \(O(x^3)\).
4. Prove using theorems mentioned in lecture that \(f(x)=x^3 + 12x\log x\) is \(O(x^3)\).
5. Prove that if \(n\) is an odd positive integer, then \(n^2\mathop{\mathbf{mod}}8=1\).