How to determine time complexity with a simple way?

Question

I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−n} + 8 \sin(2πn/256). $$

Is there a simple way how a I can determine which one of this is the true one? Because this look much more complicated then the ones we did in our class.

1. $f(n) =o(n\log_2n)$

2. $f(n) =o(2^n)$

3. $f(n) =o(n^4)$

4. $f(n) =O(n\log_2 n^n)$

5. $f(n) =O(2n + 1)$

Answer 1

Don't use the equals sign! $o(n \log_2 n)$ is the set of functions whose growth rate is strictly less than $n \log_2\,n$. So the proper expression is $f(n) \in o(n \log_2 n)$. Similarly, $O(n \log_2 n)$ is the set of functions whose growth rate is less than or equal to $n \log_2\,n$.

The simple way to determine which expressions are true is to look at the fastest growing terms. In $f(n)$ that is $4n^2$ which clearly grows faster than $2n + 1$ but slower than $n^4$.

I suggest using Python to find out for yourself:

>>> from math import *
>>> def f(n): return 4*n*(n + 2*log(n**2)**2) + e**(-n) + 8*sin(2*pi*n/256)
... 
>>> n = 999999999
>>> f(n) < 2**n
True

So $f(n) \in o(2^n)$ is likely true.

>>> f(n) < 2*n + 1
False

So $f(n) \in O(2n + 1)$ is false. While this is not a rigorous method it allows you to get a feel for the numbers. See also the answer here https://stackoverflow.com/questions/1364444/difference-between-big-o-and-little-o-notation

Answer 2

Asymptotic notation satisfies the following two useful properties: $$ \Theta(f(n)) + \Theta(g(n)) = \Theta(\max(f(n),g(n)) \\ \Theta(f(n)) \Theta(g(n)) = \Theta(f(n)g(n)) $$ Using these, you can determine that $f(n) = \Theta(4n^2\log^2 n)$.

Now you can check each of 1.-5. individually, using the fact that $n^a\log^bn = O(n^c\log^dn)$ iff $a < c$ or $a=c$ and $b \leq d$.