Comparing growth rates and common function classes - Discrete Math

Consider the recurrence relation $T(n) = 4T(n/2) + n^2\log n$ with $T(1) = 1$ . Using the Master Theorem framework, what can be concluded about the asymptotic growth of $T(n)$ ?
Answer: $T(n) = \Theta(n^2\log^2 n)$ because the extra $\log n$ factor requires the generalized case 2 analysis For the Master Theorem, we have $a = 4$ , $b = 2$ , so $n^{\log_b a} = n^{\log_2 4} = n^2$ . We need to compare $f(n) = n^2\log n$ with $n^2$ . Since $f(n) = n^2\log n = \Theta(n^2\log n)$ and $n^2\log n$ is asymptotically larger than $n^2$ but not polynomially larger (the ratio is $\log n$ ), this falls under the generalized case 2 of the Master Theorem. Specifically, $f(n) = \Theta(n^2\log^1 n)$ , so $T(n) = \Theta(n^2\log^2 n)$ . Choice A is wrong because it ignores the extra $\log n$ factor. Choice C is wrong because $f(n)$ actually dominates $n^2$ . Choice D is wrong because the regularity condition can be verified.
A recursive algorithm satisfies the recurrence relation $T(n) = 4T(n/2) + n^2\log n$ with $T(1) = 1$ . Using the Master Theorem, what is the asymptotic time complexity?
Answer: $\Theta(n^2\log^2 n)$ because we're in case 2 of Master Theorem with $k = 1$ We have $a = 4$ , $b = 2$ , so $n^{\log_b a} = n^2$ . The function $f(n) = n^2\log n$ . Since $f(n) = \Theta(n^2\log^k n)$ with $k = 1 > 0$ , we're in case 2 of the Master Theorem, giving $T(n) = \Theta(n^2\log^{k+1} n) = \Theta(n^2\log^2 n)$ . Choice A fails to account for the extra log factor from case 2. Choice C gives an intuitive but incorrect analysis. Choice D ignores the logarithmic factor in $f(n)$ .
Consider the function $G(n) = \sum_{i=1}^n \frac{1}{i^{1.1}}$ . Which statement most accurately describes the asymptotic behavior of $G(n)$ ?
Answer: $G(n) = \Theta(1)$ because the series $\sum_{i=1}^\infty \frac{1}{i^{1.1}}$ converges to a finite constant The series $\sum_{i=1}^n \frac{1}{i^{1.1}}$ is a p-series with $p = 1.1 > 1$ , so the infinite series $\sum_{i=1}^\infty \frac{1}{i^{1.1}}$ converges to some finite constant $C$ . This means $G(n) = \sum_{i=1}^n \frac{1}{i^{1.1}} \to C$ as $n \to \infty$ , so $G(n) = \Theta(1)$ . Choice A is wrong because this isn't like the harmonic series (which has $p = 1$ ). Choice B is wrong because individual terms don't determine the sum's behavior when the series converges. Choice D correctly computes the integral but misapplies it - when the integral converges, the sum approaches a constant, not the integral value.
The function $F(n) = \lfloor n^{1.5} \rfloor + \lceil \sqrt{n} \log n \rceil$ represents the complexity of a hybrid algorithm. What is the most precise asymptotic characterization of $F(n)$ ?
Answer: $F(n) = \Theta(n^{1.5})$ because the floor/ceiling functions don't affect the dominant term asymptotically For asymptotic analysis, we need to determine which term dominates. We have $n^{1.5}$ versus $\sqrt{n} \log n = n^{0.5} \log n$ . Since $\lim_{n \to \infty} \frac{n^{0.5} \log n}{n^{1.5}} = \lim_{n \to \infty} \frac{\log n}{n} = 0$ , the first term dominates. The floor and ceiling functions only change the value by at most 1, which is negligible compared to $n^{1.5}$ for large $n$ . Therefore $F(n) = n^{1.5} + o(n^{1.5}) = \Theta(n^{1.5})$ . Choice B is wrong because the second term is dominated by the first. Choice C is wrong because $\Theta$ bounds can be determined. Choice D is completely incorrect about which term dominates.
An algorithm's space complexity is given by $S(n) = \sum_{i=1}^{n} \frac{\log i}{i}$ . What is the asymptotic behavior of this space complexity?
Answer: $\Theta(\log^2 n)$ because the integral $\int_1^n \frac{\log x}{x} dx = \frac{(\log n)^2}{2}$ When analyzing asymptotic behavior of sums, you need to determine whether discrete summation or integral approximation gives the most accurate result. For sums where terms vary significantly across the range, integral approximation often provides the key insight. To find the asymptotic behavior of $S(n) = \sum_{i=1}^{n} \frac{\log i}{i}$ , consider the integral approximation: $\int_1^n \frac{\log x}{x} dx$ . Using substitution with $u = \log x$ , so $du = \frac{1}{x}dx$ , this integral becomes $\int_0^{\log n} u \, du = \frac{u^2}{2}\Big|_0^{\log n} = \frac{(\log n)^2}{2}$ . Since the function $\frac{\log x}{x}$ is positive and well-behaved over $[1,n]$ , the sum and integral have the same asymptotic growth, giving us $\Theta(\log^2 n)$ . Choice A incorrectly assumes the sum is dominated by large terms near $n$ . However, $\frac{\log n}{n}$ approaches 0 as $n \to \infty$ , so the largest individual terms actually occur in the middle range, not at the end. Choice B makes the error of treating all terms as roughly $\log n$ in size. This ignores that early terms are much smaller ( $\frac{\log 1}{1} = 0$ , $\frac{\log 2}{2} \approx 0.35$ ) and later terms decrease due to the $\frac{1}{i}$ factor. Choice D assumes the average term size is constant, but $\frac{\log i}{i}$ clearly depends on $i$ and isn't bounded by a constant. Study tip: When analyzing sums with varying terms, try integral approximation—it often reveals the true asymptotic behavior more clearly than attempting to estimate individual terms.
Consider three algorithms with time complexities $A(n) = n!$ , $B(n) = 2^{2^n}$ , and $C(n) = n^{\log n}$ . For sufficiently large $n$ , what is the correct ordering of these functions from slowest to fastest growing?
Answer: $C(n) < A(n) < B(n)$ because double exponentials grow faster than factorials, which grow faster than quasi-polynomial functions Using Stirling's approximation, $n! \approx \sqrt{2\pi n}(n/e)^n$ , so factorial is roughly exponential in $n$ . The function $2^{2^n}$ is double exponential and grows much faster than any single exponential. Meanwhile, $n^{\log n} = 2^{(\log n)^2}$ is quasi-polynomial, growing faster than any polynomial but slower than exponential functions. Choice B incorrectly orders factorial and quasi-polynomial. Choice C wrongly claims factorial grows faster than double exponential. Choice D misapplies the identity $n^{\log n} = (\log n)^n$ (which is false) and overestimates quasi-polynomial growth.
Two functions $f(n)$ and $g(n)$ satisfy $f(n) = O(g(n))$ and $g(n) = O(f(n))$ . A student concludes that $f(n)^2 = \Theta(g(n)^2)$ . Which assessment of this reasoning is correct?
Answer: The conclusion is correct because $f(n) = \Theta(g(n))$ implies $f(n)^2 = \Theta(g(n)^2)$ by the properties of big-Theta notation Since $f(n) = O(g(n))$ and $g(n) = O(f(n))$ , we have $f(n) = \Theta(g(n))$ . This means there exist positive constants $c_1, c_2$ such that $c_1 g(n) \leq f(n) \leq c_2 g(n)$ for sufficiently large $n$ . Squaring all parts (assuming functions are eventually positive, which is standard in asymptotic analysis): $c_1^2 g(n)^2 \leq f(n)^2 \leq c_2^2 g(n)^2$ . Therefore $f(n)^2 = \Theta(g(n)^2)$ . Choice B is wrong because squaring preserves asymptotic relationships for positive functions. Choice C is unnecessarily restrictive since monotonicity isn't required. Choice D is wrong because no additional conditions are needed beyond the standard assumption of eventual positivity.
A programmer implements two sorting algorithms: Algorithm X runs in $O(n \log n)$ time in the average case but $O(n^2)$ in the worst case, while Algorithm Y runs in $\Theta(n \log^2 n)$ in all cases. For which scenario is the asymptotic analysis most relevant for choosing between these algorithms?
Answer: When sorting arrays of size $n = 10^6$ with adversarially chosen data that triggers worst-case behavior When analyzing algorithm complexity, asymptotic analysis becomes most meaningful when input sizes are large enough that the dominant terms overshadow constant factors and lower-order terms, and when you're dealing with realistic worst-case scenarios that could actually occur. Algorithm X has average-case $O(n \log n)$ but worst-case $O(n^2)$ , while Algorithm Y consistently runs in $\Theta(n \log^2 n)$ . With $n = 10^6$ and adversarial data triggering the worst case, Algorithm X would perform roughly $n^2 = 10^{12}$ operations, while Algorithm Y performs about $n \log^2 n = 10^6 \times (\log 10^6)^2 \approx 10^6 \times 400 = 4 \times 10^8$ operations. This dramatic difference makes the asymptotic analysis highly relevant for choosing Algorithm Y. Choice A misunderstands when asymptotic analysis matters—it's most useful for large inputs, not small ones. Choice B is incorrect because asymptotic analysis abstracts away implementation details and hardware differences, focusing on the fundamental growth rates. Choice C correctly identifies that constant factors dominate for small inputs like $n = 50$ , but this actually makes asymptotic analysis less relevant, not more. Remember that asymptotic analysis shines when input sizes are large enough that growth rates matter more than constants, and when you're considering realistic scenarios. For exam questions, look for large $n$ values combined with conditions that could realistically occur in practice.
Consider the functions $f(n) = n^2 \log n$ and $g(n) = n^{2.1}$ . For which of the following statements about their asymptotic growth rates is true?
Answer: $f(n) = O(g(n))$ but $g(n) \neq O(f(n))$ , so $g(n)$ grows strictly faster than $f(n)$ To compare these functions, we examine $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{n^2 \log n}{n^{2.1}} = \lim_{n \to \infty} \frac{\log n}{n^{0.1}}$ . Since any polynomial (even with fractional exponent) grows faster than any logarithmic function, this limit equals 0. Therefore $f(n) = O(g(n))$ . Since the limit is 0 (not infinity), we have $g(n) \neq O(f(n))$ . Choice B is wrong because it reverses the relationship. Choice C is wrong because $f(n) \neq \Theta(g(n))$ since the limit is 0, not a positive constant. Choice D is wrong because the functions are comparable - one clearly dominates the other.
For large values of $n$ , which of the following correctly orders these functions from slowest to fastest asymptotic growth: $f_1(n) = n^{\log n}$ , $f_2(n) = (\log n)^n$ , $f_3(n) = 2^{n^{0.5}}$ , $f_4(n) = n!$ ?
Answer: $f_1(n) < f_3(n) < f_4(n) < f_2(n)$ We need to compare these functions asymptotically. First, $f_1(n) = n^{\log n} = 2^{\log n \cdot \log n} = 2^{(\log n)^2}$ . For $f_2(n) = (\log n)^n$ , taking logs: $\log f_2(n) = n \log(\log n)$ . For $f_3(n) = 2^{n^{0.5}}$ , we have $\log f_3(n) = n^{0.5}$ . For $f_4(n) = n!$ , by Stirling's approximation: $\log f_4(n) \approx n \log n - n$ . Comparing the exponents: $(\log n)^2$ vs $n^{0.5}$ vs $n \log n$ vs $n \log(\log n)$ . Since $n^{0.5}$ grows faster than $(\log n)^2$ , $n \log n$ grows faster than $n^{0.5}$ , and $n \log(\log n)$ grows faster than $n \log n$ , the order is $f_1 < f_3 < f_4 < f_2$ .
Let $f(n) = \sqrt{n} \cdot 2^{\sqrt{\log n}}$ and $g(n) = n^{0.6}$ . Which statement correctly describes the asymptotic relationship between these functions?
Answer: $f(n) = O(g(n))$ because $2^{\sqrt{\log n}}$ is polylogarithmic, making the product subpolynomial The key insight is that $2^{\sqrt{\log n}} = (2^{\log n})^{1/\sqrt{\log n}} = n^{1/\sqrt{\log n}}$ . Since $1/\sqrt{\log n} \to 0$ as $n \to \infty$ , this factor grows like a polylogarithmic function. Therefore $f(n) = \sqrt{n} \cdot (\log n)^{O(1)} = o(n^{0.6})$ . Choice A gives the right answer but wrong reasoning. Choice B incorrectly applies the general rule about exponentials. Choice C is wrong because the functions aren't asymptotically equivalent.
An algorithm's space complexity is given by $S(n) = n + \sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k$ . What is the asymptotic space complexity of this algorithm?
Answer: $S(n) = \Theta(n + 2^{\log n}) = \Theta(2n) = \Theta(n)$ since both terms have the same order Let's evaluate the sum $\sum_{k=1}^{\lfloor \log_2 n \rfloor} 2^k$ . This is a geometric series with first term $2^1 = 2$ and ratio $r = 2$ . The sum equals $\sum_{k=1}^{m} 2^k = 2(2^m - 1)/(2-1) = 2^{m+1} - 2$ where $m = \lfloor \log_2 n \rfloor$ . Since $\lfloor \log_2 n \rfloor \leq \log_2 n < \lfloor \log_2 n \rfloor + 1$ , we have $2^{\lfloor \log_2 n \rfloor} \leq n < 2^{\lfloor \log_2 n \rfloor + 1}$ . Therefore $2^{\lfloor \log_2 n \rfloor + 1} \leq 2n$ , so the sum is $\Theta(n)$ . Combined with the $n$ term: $S(n) = n + \Theta(n) = \Theta(n)$ . Choice A has the right answer but wrong reasoning about which term dominates. Choice B incorrectly analyzes the sum. Choice D has correct reasoning about the geometric series but wrong conclusion about dominance.
Functions $f_1(n) = n^2 + 1000n\log n$ , $f_2(n) = 999n^2$ , and $f_3(n) = n^2 + n^{1.9}$ are given. Which statement about their asymptotic relationships is correct?
Answer: $f_2(n) = O(f_1(n)) = O(f_3(n))$ with both $f_1(n)$ and $f_3(n)$ growing faster than $f_2(n)$ All three functions are $\Theta(n^2)$ , but we need to examine their relative growth. $f_2(n) = 999n^2$ is pure quadratic. $f_1(n) = n^2 + 1000n\log n$ has an additional $n\log n$ term that makes it grow slightly faster. $f_3(n) = n^2 + n^{1.9}$ has an additional $n^{1.9}$ term that also makes it grow faster than pure quadratic. Both $f_1$ and $f_3$ eventually dominate $f_2$ , so $f_2 = O(f_1)$ and $f_2 = O(f_3)$ . Choice B is too coarse (not tight bounds). Choice C reverses some relationships. Choice A makes an incorrect incomparability claim.
An algorithm processes data in phases, where phase $k$ requires $\frac{n^2}{2^k}$ operations for $k = 1, 2, 3, \ldots$ until $\frac{n^2}{2^k} < 1$ . What is the total number of operations as a function of $n$ ?
Answer: $\Theta(n^2)$ because the geometric series $\sum_{k=1}^{\log n} \frac{n^2}{2^k}$ is dominated by the first term When analyzing algorithms with multiple phases where work decreases geometrically, you need to carefully evaluate the sum of all phases rather than making assumptions based on the number of phases alone. The algorithm runs until $\frac{n^2}{2^k} < 1$ , which means $2^k > n^2$ , so $k > \log_2(n^2) = 2\log_2(n)$ . This gives us approximately $2\log n$ phases. The total work is $\sum_{k=1}^{2\log n} \frac{n^2}{2^k} = n^2 \sum_{k=1}^{2\log n} \frac{1}{2^k}$ . This geometric series equals $n^2 \cdot \frac{1/2 - (1/2)^{2\log n + 1}}{1 - 1/2} = n^2(1 - (1/2)^{2\log n})$ . Since $(1/2)^{2\log n} = \frac{1}{n^2}$ , the sum approaches $n^2(1 - \frac{1}{n^2}) = n^2 - 1 = \Theta(n^2)$ . The first term $\frac{n^2}{2}$ dominates all subsequent terms combined. Choice A incorrectly multiplies the number of phases by the work in the first phase, ignoring that later phases do much less work. Choice B makes the same error with vaguer reasoning about "substantial time" per phase. Choice D incorrectly computes an average and divides, which has no mathematical basis for this type of sum. Study tip: In geometric series where terms decrease rapidly, the sum is typically dominated by the first few terms, not by the number of terms. Always compute the actual sum rather than assuming it's proportional to the number of terms times the largest term.
An algorithm's running time is modeled by $T(n) = n^{1 + \sin(\log n)}$ . Which statement about the asymptotic behavior of this function is most accurate?
Answer: $T(n) = O(n^2)$ and $T(n) = \Omega(1)$ , but $T(n)$ is not $\Theta$ of any polynomial Since $\sin(\log n)$ oscillates between $-1$ and $1$ , we have $n^{1-1} \leq n^{1+\sin(\log n)} \leq n^{1+1}$ , which gives $1 \leq T(n) \leq n^2$ . Therefore $T(n) = O(n^2)$ and $T(n) = \Omega(1)$ . However, $T(n)$ is not $\Theta$ of any specific polynomial because the exponent $1 + \sin(\log n)$ oscillates infinitely often between values close to $0$ and $2$ . Choice A is wrong because averaging doesn't apply to asymptotic analysis this way. Choice C is wrong because the average value is irrelevant for big- $\Theta$ bounds. Choice D is wrong because we can still establish upper and lower bounds.
Consider the functions $f(n) = n^2 \log_2 n$ and $g(n) = n^{2.1}$ . For sufficiently large values of $n$ , which statement best describes the relationship between these growth rates?
Answer: $f(n) = O(g(n))$ but $g(n) \neq O(f(n))$ , so $g(n)$ grows asymptotically faster than $f(n)$ For any polynomial $n^k$ where $k > 2$ , we have $n^2 \log n = o(n^k)$ . Since $2.1 > 2$ , we have $n^2 \log_2 n = o(n^{2.1})$ , which means $f(n) = O(g(n))$ but $g(n) \neq O(f(n))$ . The logarithmic factor grows much slower than any positive polynomial factor. Choice B reverses the relationship. Choice C is incorrect because the functions don't have the same growth rate. Choice D is wrong because logarithm base only affects constants, not asymptotic relationships.
Functions $u(n)$ and $v(n)$ satisfy $u(n) = o(v(n))$ . A researcher claims that $u(n) + v(n) = \Theta(v(n))$ and $u(n) \cdot v(n) = o(v(n)^2)$ . Which assessment of these claims is correct?
Answer: Both claims are correct and follow directly from the properties of little-o notation and asymptotic arithmetic Since $u(n) = o(v(n))$ , we have $\lim_{n \to \infty} \frac{u(n)}{v(n)} = 0$ . For the first claim: $u(n) + v(n) = v(n)(\frac{u(n)}{v(n)} + 1) = v(n)(o(1) + 1) = v(n)(1 + o(1)) = \Theta(v(n))$ . For the second claim: $\frac{u(n) \cdot v(n)}{v(n)^2} = \frac{u(n)}{v(n)} = o(1)$ , so $u(n) \cdot v(n) = o(v(n)^2)$ . Both claims follow from standard asymptotic arithmetic rules. Choice B incorrectly suggests multiplication doesn't preserve little-o relationships. Choice C is wrong because when one function dominates (little-o case), the sum is determined by the larger function. Choice D is unnecessarily restrictive since standard asymptotic analysis handles these operations.
An algorithm's running time is measured for various input sizes, yielding $T(n) = 3n^3 + 100n^2\log n + 50n^2 + 1000n$ . If we want to classify this algorithm's time complexity using the tightest possible big-theta bound, what is the correct classification?
Answer: $\Theta(n^3)$ because the cubic term dominates all other terms asymptotically In asymptotic analysis, we keep only the fastest-growing term. Since $n^3$ grows faster than $n^2\log n$ , $n^2$ , and $n$ for sufficiently large $n$ , the tightest big-theta bound is $\Theta(n^3)$ . Choice A incorrectly includes lower-order terms. Choice C makes the common error of being misled by large coefficients - asymptotic analysis ignores constants. Choice D incorrectly combines the highest degree with a logarithmic factor that doesn't apply here.
Consider the function $h(n) = \sum_{i=1}^{n} i^2 \log i$ . Which of the following best characterizes the asymptotic growth of $h(n)$ ?
Answer: $h(n) = \Theta(n^3 \log n)$ because integration approximation gives $\int_1^n x^2 \log x \, dx \approx \frac{n^3 \log n}{3}$ When analyzing the asymptotic growth of sums involving products of polynomial and logarithmic terms, integration provides the most reliable approximation method. For large n, the sum $\sum_{i=1}^{n} i^2 \log i$ behaves similarly to the integral $\int_1^n x^2 \log x \, dx$ . To evaluate this integral, use integration by parts with $u = \log x$ and $dv = x^2 dx$ . This gives $du = \frac{1}{x}dx$ and $v = \frac{x^3}{3}$ . The integral becomes: $\int x^2 \log x \, dx = \frac{x^3 \log x}{3} - \int \frac{x^3}{3} \cdot \frac{1}{x} dx = \frac{x^3 \log x}{3} - \frac{x^3}{9}$ Evaluating from 1 to n gives approximately $\frac{n^3 \log n}{3}$ for large n, confirming that $h(n) = \Theta(n^3 \log n)$ . Choice A incorrectly assumes the largest term dominates, but this only works when terms don't grow too quickly relative to their number. Here, we have n terms each roughly of size $O(n^2 \log n)$ , requiring more careful analysis. Choice B miscalculates both the average term size and fails to account for how the sum of quadratic terms grows. Choice C incorrectly adds orders of magnitude. The $\sum i^2 = \Theta(n^3)$ fact doesn't directly apply when logarithmic factors are involved within each term. Choice D correctly applies integration approximation, the standard technique for sums of smooth, monotonic functions. Study tip: For asymptotic analysis of sums $\sum_{i=1}^n f(i)$ where f(x) is smooth and increasing, approximate with $\int_1^n f(x)dx$ rather than trying to find patterns in individual terms.

Start this quiz