Discrete Math Quiz: Comparing Growth Rates

19 questions · exam conditions

0:00

Comparing Growth RatesQuestion 1 of 19

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!$ ?

f_1(n) < f_3(n) < f_2(n) < f_4(n)

f_1(n) < f_3(n) < f_4(n) < f_2(n)

f_3(n) < f_1(n) < f_4(n) < f_2(n)

f_1(n) < f_4(n) < f_3(n) < f_2(n)

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Comparing Growth Rates

Practice Comparing Growth Rates in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Comparing Growth Rates, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

$f_1(n) < f_3(n) < f_2(n) < f_4(n)$
$f_1(n) < f_3(n) < f_4(n) < f_2(n)$ (correct answer)
$f_3(n) < f_1(n) < f_4(n) < f_2(n)$
$f_1(n) < f_4(n) < f_3(n) < f_2(n)$

Explanation: 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

n^{0.5}

n \log n

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

Question 2

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?

When sorting arrays of size $n = 100$ with random data, because asymptotic analysis applies best to small inputs
When comparing algorithms on different hardware architectures where implementation details vary significantly
When sorting arrays of size $n = 50$ where constant factors and lower-order terms dominate the runtime
When sorting arrays of size $n = 10^6$ with adversarially chosen data that triggers worst-case behavior (correct answer)

Explanation: 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.

Question 3

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?

$\Theta(n^3 + n^2\log n)$ because we must include all significant terms in the bound
$\Theta(n^3)$ because the cubic term dominates all other terms asymptotically (correct answer)
$\Theta(n^2\log n)$ because the coefficient 100 makes this term larger than $3n^3$ for practical values
$\Theta(n^3\log n)$ because we multiply the highest degree term by the logarithmic factor

Explanation: 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.

Question 4

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?

$\Theta(n^2\log n)$ because $f(n) = n^2\log n$ dominates $n^{\log_2 4} = n^2$
$\Theta(n^2\log^2 n)$ because we're in case 2 of Master Theorem with $k = 1$ (correct answer)
$\Theta(n^2\log n)$ because the recursion cost equals the work per level
$\Theta(n^2)$ because the polynomial term $n^2$ in $f(n)$ matches $n^{\log_b a}$

Explanation: 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)

Question 5

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?

$f_2(n) = O(f_1(n))$ and $f_1(n) = O(f_3(n))$ , but $f_2(n)$ and $f_3(n)$ are incomparable
$f_1(n) = \Theta(f_2(n)) = \Theta(f_3(n))$ because all three functions are quadratic
$f_3(n) = O(f_1(n)) = O(f_2(n))$ with $f_1(n)$ growing fastest asymptotically
$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)$ (correct answer)

Explanation: 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.

Question 6

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?

$C(n) < A(n) < B(n)$ because double exponentials grow faster than factorials, which grow faster than quasi-polynomial functions (correct answer)
$A(n) < C(n) < B(n)$ because $n^{\log n}$ grows faster than $n!$ due to the logarithmic exponent
$C(n) < B(n) < A(n)$ because factorials grow faster than any exponential function
$A(n) < B(n) < C(n)$ because $n^{\log n} = (\log n)^n$ which grows faster than double exponentials

Explanation: 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.

Question 7

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$ ?

$\Theta(n^2\log n)$ because there are $\log n$ phases each requiring $\Theta(n^2)$ operations
$\Theta(n^2\log n)$ because each phase takes substantial time and there are logarithmically many phases
$\Theta(n^2)$ because the geometric series $\sum_{k=1}^{\log n} \frac{n^2}{2^k}$ is dominated by the first term (correct answer)
$\Theta(n^2/\log n)$ because the average work per phase is $n^2$ divided by the number of phases

Explanation: 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.

Question 8

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?

$T(n) = \Theta(n)$ because the oscillating term averages to a constant over time
$T(n) = O(n^2)$ and $T(n) = \Omega(1)$ , but $T(n)$ is not $\Theta$ of any polynomial (correct answer)
$T(n) = \Theta(n^{1.5})$ because $\sin(\log n)$ is bounded and averages to approximately $0.5$
The function has no meaningful asymptotic bound because the oscillatory behavior prevents standard analysis

Explanation: 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.

Question 9

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?

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 (correct answer)
The conclusion is incorrect because squaring functions can change their asymptotic relationships unpredictably
The conclusion is correct only if both $f(n)$ and $g(n)$ are eventually positive and monotonic functions
The conclusion is incorrect because the squaring operation requires additional regularity conditions not given in the problem

Explanation: 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.

Question 10

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)$ ?

$G(n) = \Theta(\log n)$ because the sum behaves similarly to the harmonic series for large $n$
$G(n) = \Theta(n^{-0.1})$ because the largest term $\frac{1}{n^{1.1}}$ dominates the asymptotic behavior
$G(n) = \Theta(1)$ because the series $\sum_{i=1}^\infty \frac{1}{i^{1.1}}$ converges to a finite constant (correct answer)
$G(n) = \Theta(n^{0.9})$ because integration approximation gives $\int_1^n x^{-1.1} dx = \frac{n^{-0.1} - 1}{-0.1}$

Explanation: 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

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.

Question 11

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?

$f(n) = O(g(n))$ but $g(n) \neq O(f(n))$ , so $g(n)$ grows strictly faster than $f(n)$ (correct answer)
$g(n) = O(f(n))$ but $f(n) \neq O(g(n))$ , so $f(n)$ grows strictly faster than $g(n)$
$f(n) = \Theta(g(n))$ , so they have the same asymptotic growth rate
Neither function dominates the other asymptotically, as their growth rates are incomparable

Explanation: 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.

Question 12

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?

Both claims are correct and follow directly from the properties of little-o notation and asymptotic arithmetic (correct answer)
The first claim is correct but the second is incorrect because multiplication doesn't preserve little-o relationships
The first claim is incorrect because addition can change asymptotic relationships unpredictably when one function dominates
Both claims are incorrect because they require additional assumptions about the functions' eventual positivity and monotonicity

Explanation: 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.

Question 13

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)$ ?

$T(n) = \Theta(n^2\log n)$ because $f(n) = n^2\log n$ and $n^{\log_2 4} = n^2$ , satisfying case 2
$T(n) = \Theta(n^2\log^2 n)$ because the extra $\log n$ factor requires the generalized case 2 analysis (correct answer)
$T(n) = \Theta(n^2)$ because the recursive term $4T(n/2)$ dominates the additive term asymptotically
The Master Theorem cannot be applied because $f(n) = n^2\log n$ doesn't satisfy the regularity condition required

Explanation: 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.

Question 14

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?

$S(n) = \Theta(n)$ because the linear term dominates the geometric series for large $n$
$S(n) = \Theta(n \log n)$ because there are $\log n$ terms each contributing $O(n)$ to the sum
$S(n) = \Theta(n + 2^{\log n}) = \Theta(2n) = \Theta(n)$ since both terms have the same order (correct answer)
$S(n) = \Theta(2^{\log n}) = \Theta(n)$ because the geometric series dominates the linear term

Explanation: 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.

Question 15

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)$ ?

$F(n) = \Theta(n^{1.5})$ because the floor/ceiling functions don't affect the dominant term asymptotically (correct answer)
$F(n) = \Theta(n^{1.5} + \sqrt{n} \log n)$ because both terms contribute to the asymptotic growth significantly
$F(n) = O(n^{1.5})$ but the exact $\Theta$ bound cannot be determined due to the floor and ceiling operations
$F(n) = \Theta(\sqrt{n} \log n)$ because the ceiling operation can amplify the second term unpredictably

Explanation: 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.

Question 16

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)$ ?

$h(n) = \Theta(n^3)$ because the sum is dominated by the largest term $n^2 \log n$
$h(n) = \Theta(n^2 \log^2 n)$ because the average term is $O(n \log n)$ and there are $n$ terms
$h(n) = \Theta(n^4)$ because the sum of squares grows as $n^3$ and the logarithmic factor adds another order
$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}$ (correct answer)

Explanation: 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.

Question 17

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?

$f(n) = O(g(n))$ but $g(n) \neq O(f(n))$ , so $g(n)$ grows asymptotically faster than $f(n)$ (correct answer)
$g(n) = O(f(n))$ but $f(n) \neq O(g(n))$ , so $f(n)$ grows asymptotically faster than $g(n)$
$f(n) = \Theta(g(n))$ , meaning both functions have the same asymptotic growth rate
The relationship depends on the base of the logarithm, making comparison impossible without more information

Explanation: 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.

Question 18

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?

$\Theta(\log n)$ because the sum is dominated by the largest terms where $i$ is close to $n$
$\Theta(n\log n)$ because there are $n$ terms each roughly of size $\log n$
$\Theta(\log^2 n)$ because the integral $\int_1^n \frac{\log x}{x} dx = \frac{(\log n)^2}{2}$ (correct answer)
$\Theta(n)$ because the sum has $n$ terms and the average term size is constant

Explanation: 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.

Question 19

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?

$f(n) = O(g(n))$ because exponential functions with sublinear exponents grow slower than polynomial functions
$g(n) = O(f(n))$ because any exponential function eventually dominates any polynomial function
$f(n) = \Theta(g(n))$ because $\sqrt{\log n}$ grows slowly enough to balance the exponential with the polynomial
$f(n) = O(g(n))$ because $2^{\sqrt{\log n}}$ is polylogarithmic, making the product subpolynomial (correct answer)

Explanation: 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

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.