2
$\begingroup$

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)$

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Is there something in particular you are having trouble with? Besides, there are multiple true answers.... Also, if only one answer was true then you wouldn't need to look at $f(n)$ at all... $\endgroup$ – Steven Nov 11 '19 at 0:28
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ According to my understanding is that $e^{-n}$ is not regarded as time complexity "since it defines in all real numbers"; so it should be eliminated. $\endgroup$ – user777 Nov 18 '19 at 16:52
  • $\begingroup$ Why? For example $1 \in \Omega(e^{-n})$ would certainly be a valid but somewhat misleading way of specifying time complexity. $\endgroup$ – Björn Lindqvist Nov 18 '19 at 17:47
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.