# Homework #5

Due in lecture, Thursday April 4Monday April 8. Please do the homework in a workbook.

# 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$$.