A3 answers

[Jennifer Webb]

Here are my answers for A3, Section 2 part 1:

1. C

2. II

3. Algorithm Smart: O(n) , Algorithm NotSmart: O(n); Algorithm Foolish does not terminate 

4. 1. summation value = n; value in theta notation= Θ(n)

    2. summation value = n(n+1)/2; value in theta notation=Θ(n²)

    3. summation value = n(n+1)(2n+1)/6; value in theta notation = Θ(n³)

    4. summation value = n²(n+1)²/4 ; value in theta notation = Θ(n⁴)

5. B

6. T is always a spanning tree but not necessarily minimal 

7. True

8. True

9. True

I will post the work tomorrow night..

[Jennifer Webb]

Here's all my work

[Christopher Rivas]

I am not sure about your work for #7. I've never seen that you can say "lim n^2 = lim n^3",
but I do agree that #7 is true because you can always find a constant M such that f (x) < M * g(x), where f(x) is the original function, and g(x) = n^3 for ANY x0 > x (the theory thing says ALL, but meh)