Which of the following statements are true? Time Complexities

But I'm not sure if I'm doing it right. Here is what I have so far:

a) $f_1 = O(f_2)$

b) Not Equal

c) Not Equal

Justification: $n^2 = 1000^2 =$ 1 million while $(1000)\log^4 (1000) = 2.27..$ so we know that $f(x) \notin O(g(x))$

d) $f_1 = O(f_2)$

Justification: $\log(n) = \log(1000) = 6.907..$ and $\log(n^5) = 34.538..$

so we know that $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n)$, $∀$ $n≥n_0|$ $\therefore f_1 = O(f_2)$

e) $f_1 = O(f_2)$

f) Not Equal

• Um, you're not even showing what your functions are. How is anybody going to tell whether your claims about them are right, then? – Henning Makholm Sep 7 '15 at 23:12
• Ahh my mistake!! – Yusha Sep 7 '15 at 23:16
• @HenningMakholm Fixed. – Yusha Sep 7 '15 at 23:17
• What do you mean by Not Equal? Do you mean that none ofthe equations holds? This would be wrong. – philipph Sep 8 '15 at 12:56

1 Answer

Your justifications are not strong enough. Calculating some values for specific $n$ is not enough. You either have to give specific values for $c$ and $n_0$ such that the definitions for $\mathcal{O}$, $\Omega$, or $\Theta$ are fulfilled, or you have to show that for any given $c$ and $n_0$ there exists an $n \geq n_0$ such that the definition is not fulfilled.

To show that $f_1 = \mathcal{O}(f_2)$ you have to give constants $c$ and $n_0$ such that $$f_1(n) \leq c \cdot f_2(n)$$ for all $n \geq n_0$.

To show that $f_1 \neq \mathcal{O}(f_2)$ you have to show that for any constants $c$ and $n_0$ you can give an $n \geq n_0$ such that $$f_1(n) > c \cdot f_2(n).$$

Similarly for $f_1 = \Omega(f_2)$ and $f_1 \neq \Omega(f_2)$. $f_1 = \Theta(f_2)$ can only hold if $f_1 = \mathcal{O}(f_2)$ and $f_1 = \Omega(f_2)$.

Let me guide you through the prove why $f_1 = \mathcal{O}(f_2)$ for a) and the other two equations do not hold.

To show that $f_1 = \mathcal{O}(f_2)$ you can set $c = 500$ and $n_0 = 10$. Then $1 \leq \log n$ and, thus, $$f_1(n) = 1000 n - 100 \leq 1000 n \log n + 3000n = 500 f_2(n)$$ for all $n \geq 10$. This shows that $f_1 = \mathcal{O}(f_2)$.

To show that $f_1 \neq \Omega(f_2)$, let constants $c$ and $n_0$ be given. If $n \geq n_0$ is chosen such that $\log n > \frac{501 - 3c}{c}$ and $n > 50$ then \begin{align*} c \cdot f_2(n) - f_1(n) &= c \cdot (2 n \log n + 6n) - 1000n - 100 \\ &= (2 c \log n + 6 c - 1000) n - 100 \\ &> (2 (501 - 3c) + 6c - 1000)n - 100 \\ &= 2n - 100 > 0 \end{align*} which is equivalent to $c \cdot f_2(n) > f_1(n)$ for such $n$. Thus, $f_1 \neq \Omega(f_2)$. This directly implies $f_1 \neq \Theta(f_2)$.

• Can I ask how you came up with $501 - 3c$? – Yusha Sep 8 '15 at 23:42
• I came up with the bounds on $n$ by starting with $c \cdot f_2(n) > f_1(n)$ which holds true if $c \cdot (2n \log n + 6n) > 1000n - 100$ which can be further transformed to $(2c \log n + 6c - 1000) n > 100$. I split this inequality into two inequalities $2c \log n + 6c - 1000 > 2$ and $n > 50$. If you transform the first inequality a little further you get $\log n > \frac{501-3c}{c}$. – philipph Sep 10 '15 at 7:16
• These transformations will be different for every pair of functions. I guess that for a) these transformations are rather easy compared to c), d), and h). I suspect the transformations to be rather difficult for these functions. – philipph Sep 10 '15 at 7:19