Problem Set 2

1. Compute each of the following summations by hand. Show all of your work.

$$\sum _{j=0}^{5}j$$

$$\sum _{k=-2}^2(1-k{)}^2$$

$$\sum _{i=0}^4{3}^i$$

$$\sum _{i=3}^7\lfloor \frac{i}{4}\rfloor$$

---

2. Compute the Big-O value for $f(n)=2^{n+1}+n$. Justify your answer with a few sentences of explanation.

---

3. Compute the Big-$\Omega$ value for $f(n)=n^2+4n+5$. Justify your answer with a few sentences of explanation.

---

4. Compute the Big-$\Theta$ value for $f(n)=10nlogn$. Justify your answer with a few sentences of explanation.

---

5. Prove that the following relation is true.

$$\sum _{i=0}^{N}i=\frac{N(N+1)}{2}$$

Hint!

You can use a proof by induction.

---

6. Prove that the number $\sqrt{2}$ is irrational.

Hint!

You can use a proof by contradiction.

---

7. According to this reference, the Bubble Sort algorithm has a worst case time complexity of $O(n^2)$, but a best case time complexity of $O(n)$. Does this mean that Bubble Sort is more performant than an algorithm like Quicksort with a worst case and best case complexity of $O(nlogn)$? Why don’t we just use Bubble Sort in large systems, all the time?