The exercise you're asking about concerns disproving two mathematical statements involving the Big-O notation by providing counterexamples. The problem is structured as follows:

Given:

• $f_1(n) = O(g_1(n))$ and
• $f_2(n) = O(g_2(n))$,

You are asked to disprove the following statements:

a. $f_1(n) - f_2(n)$ is $O(g_1(n) - g_2(n))$.

b. $\frac{f_1(n)}{f_2(n)}$ is $O\left(\frac{g_1(n)}{g_2(n)}\right)$.

Disproving by Counterexample:

Part a:

We want to find an example where $f_1(n) - f_2(n)$ is not bounded by $O(g_1(n) - g_2(n))$.

Consider the following counterexample:

• Let $f_1(n) = n^2 + 1$, $f_2(n) = n^2$,
• Let $g_1(n) = n^2 + n$, $g_2(n) = n$.

Both $f_1(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$ are true:

• $f_1(n) = n^2 + 1 = O(n^2 + n)$,
• $f_2(n) = n^2 = O(n)$.

However:

• $f_1(n) - f_2(n) = (n^2 + 1) - n^2 = 1$, which is a constant,
• $g_1(n) - g_2(n) = (n^2 + n) - n = n^2$.

Clearly, $1$ is not $O(n^2)$. Thus, this provides a counterexample, disproving the first statement.

Part b:

We need to find an example where $\frac{f_1(n)}{f_2(n)}$ is not bounded by $O\left(\frac{g_1(n)}{g_2(n)}\right)$.

Consider this counterexample:

• Let $f_1(n) = n^2$, $f_2(n) = n$,
• Let $g_1(n) = n^2$, $g_2(n) = n^2$.

Here, both $f_1(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$ hold:

• $f_1(n) = n^2 = O(n^2)$,
• $f_2(n) = n = O(n^2)$.

However:

• $\frac{f_1(n)}{f_2(n)} = \frac{n^2}{n} = n$,
• $\frac{g_1(n)}{g_2(n)} = \frac{n^2}{n^2} = 1$.

Clearly, $n$ is not $O(1)$, disproving the second statement as well.

These two examples disprove both statements by showing cases where the Big-O relation does not hold.

Do you need further details or have questions? Here are some related questions for further exploration:

1. How does Big-O notation compare growth rates of functions?
2. What are typical functions used in Big-O notation analysis (e.g., polynomials, logarithmic, exponential)?
3. What is the meaning of asymptotic upper bounds in Big-O notation?
4. Can we have a function that is both $O(g(n))$ and $O(h(n))$ where $g(n) \neq h(n)$?
5. How does Big-$\Omega$ and Big-$\Theta$ notation differ from Big-O?

Tip: When disproving statements in Big-O notation, always try to come up with edge cases (e.g., constants, powers) to test whether the assumptions hold.