Question Discussion & Solution

🔑 Key Points

• Big O notation (\(O\)): \(f(n) = O(g(n))\) if there exist positive constants \(c\) and \(n_0\) such that \(0 \le f(n) \le c \cdot g(n)\) for all \(n \ge n_0\).
• To determine the relationship, we can evaluate the limit: \(\lim_{n \to \infty} \frac{f(n)}{g(n)}\).
• For \(f(n) = n^3 + 100n^2\) and \(g(n) = n^4\), the limit is \(\lim_{n \to \infty} \frac{n^3 + 100n^2}{n^4} = \lim_{n \to \infty} \left(\frac{1}{n} + \frac{100}{n^2}\right) = 0\).
• Since the limit is \(0\), it implies that \(f(n)\) grows strictly slower than \(g(n)\). This means \(f(n) = O(g(n))\) and \(f(n) = o(g(n))\) are true.
• It also implies that \(f(n) \ne \Omega(g(n))\), \(f(n) \ne \Theta(g(n))\), and \(f(n) \ne \omega(g(n))\).
• Among the given options, \(f(n) = O(g(n))\) is the only correct statement.