Question

1. A. (20p) Give a Big-O estimate that is as good as possible for each of the following functions.

i. (n^3 + n)(logn + n)

ii. (n + 1000)(logn + 1)

B. (15p) If these are complexities of algorithms that solve the same problem, which one would you

prefer? Why?

C. (15p) Considering the Big-O complexity, how many times is your choice faster with respect to the

other solution for an input size of 2^16?

Note: The base of logarithm is 2

Answer 1

A.i. $(n^3 + n)(\log_2 n + n)=n^4(1+n^{-2})(1+\log_2 n / n)=O(n^4)$

ii. $(n + 1000)(\log_2n + 1) = n\log_2n(1 + \frac{1000}{n})(1+\frac{1}{\log_2n}) = O( n\log_2n)$ B. The second estimate of the complexity is preferable, as its growth is much more slower.

C. If n=2¹⁶ then

$n^4 = 2^{64}$ ,

$n\log_2n = 2^{16}\cdot 2^4 = 2^{20}$

and the second estimate of the complexity is 2⁴⁴ times better.