0
$\begingroup$

enter image description here enter image description here

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

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

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

$\endgroup$
  • $\begingroup$ Can I ask how you came up with $501 - 3c$? $\endgroup$ – Yusha Sep 8 '15 at 23:42
  • $\begingroup$ 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}$. $\endgroup$ – philipph Sep 10 '15 at 7:16
  • $\begingroup$ 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. $\endgroup$ – philipph Sep 10 '15 at 7:19

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.