Problem Set 2

1. Show that $f(n)=3$ (a constant) is $O(1)$. Justify your answer with a proof.

---

2. Show that $f(n)=2^{n+1}+n$ is $O(2^n)$. Justify your answer with a proof.

---

3. Show that $f(n)=n^2+4n+5$ is $\Omega (n^2)$. Justify your answer with a proof.

---

4. Show that $f(n)=10nlogn$ is $\Theta (nlogn)$. Justify your answer with a proof.

---

5. Prove by induction that $n^3+2n$ is divisible by $3$ for every non-negative integer n.

---

6. 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?

---

7. Suppose I create a data structure called MyCoolStructure which has four operations. Each of the operations runs in O(1) time:

MyCoolStructure mcs;
 
mcs.insert_first(x); // inserts "x" at the front of the structure
mcs.insert_last(x);  // inserts "x" at the end of the structure
mcs.delete_first();  // deletes the element at the front of the structure and returns it to the user
mcs.delete_last();   // deletes the element at the end of the structure and returns it to the user

• Write the pseudocode for a function called void swap_ends(MyCoolStructure mcs) which swaps the first and last items in the data structure. Be sure to handle the edge cases where the data structure is empty or has only one element!
• What is the Big-O time complexity of this function? Justify your answer with a proof.

8. What is the difference between “wall time”, “user cpu time”, and “kernel cpu time” in the context of benchmarking code?