Question

Let f(n) = 560*n^3 +3*n+107 and g(n) = 3*n^3 +5000*n^2. Which of the following is true?
a) f(n) is O(g(n)), but g(n) is not O(f(n))
b) g(n) is O(f(n)), but f(n) is not O(g(n))
c) f(n) is not O(g(n)) and g(n) is not O(f(n))
d) f(n) is O(g(n)) and g(n) is O(f(n))

Answer 1

Answer on Question #53336 – Math – Algorithms | Quantitative Methods

Question Let $f(n) = 560n^3 + 3n + 107$ and $g(n) = 3n^3 + 5000n^2$. Which of the following is true?

a) $f(n)$ is $O(g(n))$, but $g(n)$ is not $O(f(n))$

b) $g(n)$ is $O(f(n))$, but $f(n)$ is not $O(g(n))$

c) $f(n)$ is not $O(g(n))$, and $g(n)$ is not $O(f(n))$

d) $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$.

Solution

In computer science "$f(n)$ is $O(g(n))$" means that $f(n)$ growth asymptotically no faster than $g(n)$. So there exist positive numbers $k_{1}$ and $k_{2}$ such that inequalities

$$k _ {1} g (n) \leq f (n) \leq k _ {2} g (n)$$

hold true.

Search bounds for $f(n)$ and $g(n)$:

$$\begin{array}{l} f (n) = 5 6 0 n ^ {3} + 3 n + 1 0 7 \leq 5 6 0 n ^ {3} + 3 n ^ {3} + 1 0 7 = 5 6 3 n ^ {3} + 1 0 7 \leq 5 6 4 n ^ {3} + 1 0 7 = \\ = 1 8 8 \cdot 3 n ^ {3} + 1 0 7 \leq 1 8 8 \cdot (3 n ^ {3} + 5 0 0 0 n ^ {2}) = 1 8 8 \cdot g (n), \text { hence } \frac {1}{1 8 8} f (n) \leq g (n); \end{array}$$ $$\begin{array}{l} g (n) = 3 n ^ {3} + 5 0 0 0 n ^ {2} \leq 3 n ^ {3} + 5 0 0 0 n ^ {3} = 5 0 0 3 n ^ {3} \leq 5 0 4 0 n ^ {3} = 9 \cdot 5 6 0 n ^ {3} \leq \\ \leq 9 (5 6 0 n ^ {3} + 3 n + 1 0 7) = 9 f (n), \text { hence } \frac {1}{9} g (n) \leq f (n). \end{array}$$

We showed that

$$\frac {1}{9} g (n) \leq f (n) \leq 1 8 8 g (n)$$

and

$$\frac {1}{1 8 8} f (n) \leq g (n) \leq 9 f (n)$$

We have polynomial expressions of the same order, hence answer is d) $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$.

Answer: d) $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$.

www.AssignmentExpert.com