Asymptotic notation (Big-O, Big-Theta, Big-Omega) - Discrete Math

1. Consider functions $f_1(n) = n^{\log_3 2}$ and $f_2(n) = 2^{\log_2 n}$. If we define $f_3(n) = f_1(n) \cdot f_2(n)$, which asymptotic bound correctly characterizes $f_3(n)$?
   Answer: $f_3(n) = \Theta(n^{1 + \log_3 2})$ because logarithmic bases convert multiplicatively in products First, $f_2(n) = 2^{\log_2 n} = n$ by the identity $a^{\log_a x} = x$. Therefore $f_3(n) = f_1(n) \cdot f_2(n) = n^{\log_3 2} \cdot n = n^{\log_3 2 + 1} = n^{1 + \log_3 2}$. Choice B incorrectly treats $\log_2 n$ as remaining in the exponent. Choice C gives an unrelated expression. Choice D incorrectly doubles the original exponent.
2. If $f(n) = 2^{n+1} + 3^{n-1}$ and $g(n) = 4 \cdot 3^n$, which asymptotic relationship holds between $f(n)$ and $g(n)$?
   Answer: $f(n) = \Theta(g(n))$ because both functions have $3^n$ as the dominant term When comparing asymptotic growth rates of functions with multiple exponential terms, you need to identify which term dominates and then compare the dominant terms between functions. Let's analyze each function's growth. For $f(n) = 2^{n+1} + 3^{n-1}$, as $n$ grows large, the $3^{n-1}$ term will dominate because $3^n$ grows much faster than $2^n$. We can rewrite this as $f(n) = 2 \cdot 2^n + \frac{1}{3} \cdot 3^n$, showing that $f(n) \sim \frac{1}{3} \cdot 3^n$ for large $n$. For $g(n) = 4 \cdot 3^n$, the dominant term is clearly $4 \cdot 3^n$. Since both functions are dominated by terms proportional to $3^n$, we have $f(n) = \Theta(g(n))$. Specifically, $\frac{1}{12} \cdot 3^n \leq f(n) \leq 5 \cdot 3^n$ for sufficiently large $n$, and $g(n) = 4 \cdot 3^n$, confirming the theta relationship. Choice A is correct because both functions indeed have $3^n$ as their dominant term. Choice B incorrectly suggests $f(n)$ grows slower than $g(n)$, missing that $f(n)$'s $3^{n-1}$ term dominates its $2^{n+1}$ term. Choice C makes the opposite error, suggesting $g(n)$ grows slower due to misunderstanding which term dominates in $f(n)$. Choice D incorrectly focuses on the different exponential bases without recognizing that $3^n$ dominates in both functions. Study tip: When comparing functions with multiple exponential terms, always identify the fastest-growing term first—exponentials with larger bases will always eventually dominate those with smaller bases.
3. Let $f(n) = n!$ and $g(n) = n^n$. Which statement correctly compares their asymptotic growth rates?
   Answer: $f(n) = O(g(n))$ and $g(n) \neq O(f(n))$ because $n^n$ grows faster Using Stirling's approximation, n! ≈ √(2πn)$(n/e)^n$. Comparing with $n^n$, we get n!/$n^n$ ≈ √(2πn)/$e^n$ → 0 as n → ∞. Therefore f(n) = o(g(n)), which implies f(n) = O(g(n)) and g(n) ≠ O(f(n)). Choice A is wrong about factorials being slower than all exponentials. Choice B is incorrect because they're not asymptotically equivalent. Choice C reverses the relationship.
4. Consider functions where $f(n) = O(n^2)$ and $g(n) = \Omega(n \log n)$. If $h(n) = f(n) \cdot g(n)$, what is the tightest upper bound we can guarantee for $h(n)$?
   Answer: No finite upper bound can be guaranteed without more information about the functions Since g(n) = Ω(n log n), g(n) could grow arbitrarily fast (e.g., g(n) = $n^{100}$). Even though f(n) = O(n²), the product f(n)·g(n) could be as large as O(n²)·$n^{100}$ = O($n^102$) or even larger. Without an upper bound on g(n), we cannot establish any finite upper bound for h(n). Choice A assumes g(n) = O(n log n). Choice B makes the same error. Choice C misunderstands how Ω works in products.
5. Which of the following statements about the function $f(n) = n^{\log n}$ is correct?
   Answer: $f(n) = \omega(n^k)$ for any constant $k$ but $f(n) = o(2^n)$ Since $n^{log n}$ = $2^{log n · log n}$ = $2^{(log n)²}$, this function grows faster than any polynomial $n^k$ (because (log n)² → ∞), but slower than $2^n$ (because (log n)² = o(n)). Therefore f(n) = ω($n^k$) for any constant k, and f(n) = o($2^n$). Choice A is wrong because f(n) grows super-polynomially. Choice B has the wrong asymptotic equivalence. Choice D is incorrect because n! grows much faster than $n^{log n}$.
6. Let $g(n) = \sum_{i=1}^{n} i \log i$ and $h(n) = n^2 \log n$. Which statement correctly describes the relationship between $g(n)$ and $h(n)$?
   Answer: $g(n) = O(h(n))$ and $g(n) = \Omega(h(n))$, so $g(n) = \Theta(h(n))$ Using integral approximation, ∑(i=1 to n) i log i ≈ ∫(1 to n) x log x dx. By integration by parts, this integral equals (n² log n)/2 - n²/4 + C, which is Θ(n² log n). Since h(n) = n² log n, we have g(n) = Θ(h(n)). Choice B is wrong because g(n) = Ω(h(n)). Choice C is wrong because g(n) = O(h(n)). Choice D is wrong because both relationships hold.
7. Consider the function $h(n) = \sum_{k=1}^{\sqrt{n}} k^2 \log k$. Which asymptotic characterization is most precise for $h(n)$?
   Answer: $h(n) = \Theta(n^{3/2} \log n)$ because the logarithmic term in the largest summand affects the total Using integral approximation: $\sum_{k=1}^{\sqrt{n}} k^2 \log k \approx \int_1^{\sqrt{n}} x^2 \log x \, dx$. Using integration by parts: $\int x^2 \log x \, dx = \frac{x^3}{3}\log x - \frac{x^3}{9} + C$. Evaluating from 1 to $\sqrt{n}$: the dominant term is $\frac{(\sqrt{n})^3}{3}\log(\sqrt{n}) = \frac{n^{3/2}}{3} \cdot \frac{\log n}{2} = \Theta(n^{3/2} \log n)$. Choice A misses the logarithmic factor. Choice C incorrectly computes the effect of the summation limit. Choice D gives the right answer but the reasoning about "throughout" is imprecise.
8. Consider the function $f(n) = 3n^2 \log n + 5n^2 + 2n \log n + 100$. Which of the following statements about the asymptotic behavior of $f(n)$ is correct?
   Answer: $f(n) = \Theta(n^2 \log n)$ and $f(n) = O(n^3)$ The dominant term in f(n) is 3n² log n. The function f(n) = Θ(n² log n) because both 3n² log n and 2n log n contribute to the n² log n growth, while 5n² grows slower. Since n² log n = o(n³), we also have f(n) = O(n³). Choice A is wrong because f(n) grows faster than n². Choice C is wrong because f(n) = O(n² log n). Choice D is wrong because f(n) grows faster than n².
9. If $f(n) = \Theta(n^3)$ and $g(n) = O(n^2 \log n)$, what can be concluded about $h(n) = f(n) + g(n)$?
   Answer: $h(n) = \Theta(n^3)$ because $f(n)$ dominates $g(n)$ asymptotically Since f(n) = Θ(n³), there exist constants c₁, c₂ such that c₁n³ ≤ f(n) ≤ c₂n³ for large n. Since g(n) = O(n² log n) and n² log n = o(n³), g(n) becomes negligible compared to f(n). Therefore h(n) = f(n) + g(n) = Θ(n³). Choice A is wrong because h(n) = Ω(n³). Choice B uses incorrect notation. Choice D is wrong because h(n) = Θ(n³).
10. Consider the recurrence relation $T(n) = 3T(n/2) + n^2$ with $T(1) = 1$. Using the Master Theorem, what is the asymptotic complexity of $T(n)$?
    Answer: $T(n) = \Theta(n^2)$ because $n^2$ dominates $n^{\log_2 3}$ In the Master Theorem with T(n) = aT(n/b) + f(n), we have a = 3, b = 2, f(n) = n². The critical exponent is log₂ 3 ≈ 1.585. Since f(n) = n² and 2 > log₂ 3, we're in case 3 of the Master Theorem. We need to verify that f(n) = Ω($n^{log₂ 3 + ε}$) for some ε > 0, which holds, and the regularity condition af(n/b) ≤ cf(n), which also holds. Therefore T(n) = Θ(n²). Choice A confuses the comparison direction. Choice C applies the wrong case. Choice D uses incorrect reasoning.

Start this quiz