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.