I'm stuck on a few big-O notation True or False questions, any insight would be appreciated

  1. For any two positive constants $c,d > 0$ we have $n^c = o(2^{dn})$

Answer: False let $n = 10, c = 1000, d = 1$. I gave a counter example, but how can I go about proving this more formally using limits.

  1. For any two functions $f,g$ where $n$ is any real positive number, either $f = O(g)$ or $g = O(f)$

Answer: True, this one makes sense to me as $O$ depicts $\geq$ meaning whatever values we pick, whether we put $value 1 \geq value 2$ or $value 2 \geq value 1$ one of these must be true.

  1. For any functions $f,g$ where $n$ is any real positive number, $\sqrt{f(n)} + \sqrt{g(n)} = \Omega(\sqrt{f(n)+g(n)})$

Answer: True, can plug in test cases where $f(n) = 1 g(n) = 9$, however I am not sure as how to formally prove this. I understand I want to use the following "There exists some $C_1, C_2 > 0$ and there exists some real number $N$ such that for all $n > n_0$ we have $C_1 \cdot \sqrt{f(n)+g(n)} < \sqrt{f(n)} + \sqrt{g(n)} < C_2 \cdot \sqrt{f(n)+g(n)}$

  1. $1^c + 2^c + ... + n^c = \Theta(n^{c+1})$ for every $C \geq 0$

Answer: I am inclined to say False as $n^c \neq (n^{c+1})$ (exponents will never equal each other) therefore we would never be able to find an $C_1, C_2$ such that $C_1n^c < (n^{c+1}) < C_2 n^c$. Again I'm lost on here on how to go about proving this formally.

Any help on steering me in the right direction in terms of proving this formally would be appreciated. I understand that I have to use the formal definitions of Big O, however on some of these I am completely lost on where to even begin.

  • 1
    $\begingroup$ You will have to use the formal definition of asymptotic notation: That $f = O(g)$ if there exists a $c \in \mathbb{R}_{+}$ and an $n_0 \in \mathbb{N}$ such that $f(n) \leq c \cdot g(n)$ whenever $n \geq n_0$. On a completely different note: I have cleaned up your MathJax formatting; it really was quite clumsy. $\endgroup$ – Hans Hüttel Oct 3 '17 at 21:12
  • 1
    $\begingroup$ Your answers for 1, 2, and 4 are wrong. $\endgroup$ – Antonio Vargas Oct 3 '17 at 21:38

Your Answer

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

Browse other questions tagged or ask your own question.