Solutions week 2 - Complexity

1

$\log n$, $4n$, $n \log n$, $5n^2+n$, $3n^3$, $n^4$

2

$$\begin{align} T(n) = & 2^n \times 1e^{-6}\\ T(n) = & 5e^9 \times 365 \times 24 \times 60 \times 60 \end{align}$$ so $$\begin{align} 2^n \times 1e^{-6} = & 5e^9 \times 365 \times 24 \times 60 \times 60\\ 2^n = & 5e^9 \times 365 \times 24 \times 60 \times 60 \times 1e^6\\ 2^n = & 1.5768e^{23}\\ \log_2 (2^n) = & \log_2 1.5768e^{23}\\ n = & 77.06134586390338 \end{align}$$

Thus, max 77 steps.

3

$n = 50$

• $10 \times 2^n = 11258999068426240 \approx 357 \space\text{years}$

  -> unreasonable

• $10000 \log_2 n = 56438.561... \space\text{microsec} < 1 \space\text{seconds}$

  -> reasonable, no problem

• $100000 n = 5000000 = 5 \space\text{seconds}$

  -> reasonable

• $10 n! = 30414093201713... \approx 9.6e51 \space\text{years}$

  -> unreasonable

4

$O(34x + x^2) = O(34x) + O(x^2) = O(x) + O(x^2) = O(x^2)$

$O(1x+2x+3x+4x+5x+6x+7x) = O(28x) = O(x)$

$$\begin{align} O(10^{4000} x + 0.005 x^2 + \frac{103}{x^3}) = & O(10^{4000} x) + O(0.005 x^2) + O(\frac{103}{x^3}) \\ = & O(x) + O(x^2)\\ = & O(x^2) \end{align}$$

$\frac{103}{x^3}$ approaches 0 as $x$ approaches infinity

$$\begin{align} O(10 \log_2 x + 2 \log_{10} x) = & O(10 \log_2 x) + O(2 \log_{10} x)\\ = & O(\log x) + O(\log x)\\ = & O(\log x) \end{align}$$

The base of the logarithm is irrelevant in big-O notation since using the logarithm law we have $\log_a n = \frac{\log_b n}{\log_b a}$ for any constants $a$ and $b$, and since $\log_b a$ is constant we have $O(\log_{10} n) = O(\log n)$.

$O(2^x + 10^x) = O(2^x) + O(10^x) = O(10^x)$

$10^x$ and $2^x$ are different as they do not differ by a constant, since $\frac{10^x}{2^x} = 5^x$ and so $O(10^x) \neq O(2^x)$.

$$\begin{align} O((x-2)(x-1)x) = & O(x-2) \times O(x-1) \times O(x)\\ = & O(x) \times O(x) \times O(x)\\ = & O(x \times x \times x)\\ = & O(x^3) \end{align}$$

5

Given a size of $n$, it takes $O(n)$ time in the worst case as an increase (resize) in size of the internal array might be needed.

Assuming the ArrayList is initially empty, adding $O(n)$ elements takes $O(n)$ time. See for example lecture slides for explanation.

6

See the ArrayList javadoc documentation. It shifts n - 1 elements to the left in the worst case (that is if we remove the first element), so $O(n)$.

If we are allowed to change the order of the elements, we can do a delete in constant time. For example, by swapping the to be removed element with the last element and decreasing the size of the list by one.

7

See for example Duplicates.java and NoDups.hs.