Homework 2

Download the corresponding ipynb file here: hw-2.ipynb.

Big-O Notation

Exercise 1 (3 points) Is 2^{n+1}=\mathcal O(2^n)? Justify your answer using Definition 3.1.

Solution. The answer is 2^{n+1}=\mathcal O(2^n).

In order to show this, we need to find just one combination of position constants c and n_0 such that 2^{n+1} \leq c\cdot 2^n\text{ for all }n\geq n_0.

Note that 2^{n+1}=2\cdot 2^n. We can choose c=2 and n_0=1 to see that 2^{n+1}\leq 2\times 2^n\text{ for all }n\geq 1.

The above inequality is, in fact, can be replaced with equality.

Exercise 2 (3 points) Is 2^{2n}=\mathcal O(2^n)? Justify your answer using Definition 3.1.

Solution. The answer is negative, i.e. 2^{2n}\neq \mathcal O(2^n).

We prove by contradiction.

Let us assume the contrary that 2^{2n}=\mathcal O(2^n), i.e there exist some positive constants c and n_0 such that 2^{2n}\leq c\times 2^n\text{ for all }n\geq n_0. The relation would imply that c\geq\frac{2^{2n}}{2^n}=2^n\text{ for all }n\geq n_0. Since the above relation must be true for any large n one chooses, our c cannot really be a constant. This is a contradiction to our assumption in the beginning that c is a constant.

Therefore, we conclude that 2^{2n}\neq \mathcal O(2^n).

Exercise 3 (3 points) Using Definition 3.1, show that the function 100n\lg{n} is \mathcal O(n^2-1).

Solution. In order to gain intuition, we inspect the following plot first. We choose c=200. You may try out different constants c in front of n^2-1.

It looks like the combination c=200 and n_0=2 should suffice. We now prove it by noting, from our first class, a mathematical fact: \lg{n}\leq n\text{ for any }n.

Now, for any n\geq2: \begin{align*} &100n\lg{n} \\ &\leq 100n\cdot n,\text{ since }\lg{n}\leq n\text{ as noted above} \\ &= 200n^2-100n^2 \\ &\leq200n^2-200,\text{ since }n\geq2\\ &=200(n^2-1). \end{align*} Hence the result.

🏅 Bonus: As it appears in the plot, n_0=1 should also work with c=200. Can you prove it?

Exercise 4 (1+1 points) Describe the difference between an upper bound and a tight upper bound? Explain using an example.

Exercise 5 (1+1 points) Provide an example of an \mathcal O(1) and \mathcal O(n) algorithm.

Exercise 6 (🏅 Bonus:) If f(n)=\mathcal O(g(n)), then 2^{f(n)} = \mathcal O(2^{g(n)}). True or false? Justify your answer.

Powerset Generation

Exercise 7 (5 points) Write a Python code to generate all the subsets of a given list.

Exercise 8 (2 points) If the input list has n elements, describe the time complexity of your code. A thorough explanation is required.