Discrete Math Quiz: Asymptotic Notation

10 questions · exam conditions

0:00

Asymptotic NotationQuestion 1 of 10

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

g(n) = O(h(n))

and

g(n) = \Omega(h(n))

, so

g(n) = \Theta(h(n))

g(n) = O(h(n))

but

g(n) \neq \Omega(h(n))

because the sum grows slower

g(n) = \Omega(h(n))

but

g(n) \neq O(h(n))

because of the logarithmic factor

Neither

g(n) = O(h(n))

nor

g(n) = \Omega(h(n))

holds due to oscillation

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Asymptotic Notation

Practice Asymptotic Notation 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 Asymptotic Notation, 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

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

$g(n) = O(h(n))$ and $g(n) = \Omega(h(n))$ , so $g(n) = \Theta(h(n))$ (correct answer)
$g(n) = O(h(n))$ but $g(n) \neq \Omega(h(n))$ because the sum grows slower
$g(n) = \Omega(h(n))$ but $g(n) \neq O(h(n))$ because of the logarithmic factor
Neither $g(n) = O(h(n))$ nor $g(n) = \Omega(h(n))$ holds due to oscillation

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

Question 2

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

$h(n) = O(n^3)$ but we cannot determine if $h(n) = \Omega(n^3)$
$h(n) = \Theta(n^3 + n^2 \log n)$ which simplifies to $\Theta(n^3)$
$h(n) = \Theta(n^3)$ because $f(n)$ dominates $g(n)$ asymptotically (correct answer)
$h(n) = O(n^3)$ and $h(n) = \Omega(n^2 \log n)$ but $h(n) \neq \Theta(n^3)$

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

Question 3

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

$f(n) = \Theta(g(n))$ because both functions have $3^n$ as the dominant term (correct answer)
$f(n) = O(g(n))$ but $f(n) \neq \Omega(g(n))$ since $3^n$ dominates $2^n$
$g(n) = O(f(n))$ but $g(n) \neq \Omega(f(n))$ due to the $2^{n+1}$ term
Neither $f(n) = O(g(n))$ nor $g(n) = O(f(n))$ due to different exponential bases

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

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.

Question 4

Consider the function $h(n) = \sum_{k=1}^{\sqrt{n}} k^2 \log k$ . Which asymptotic characterization is most precise for $h(n)$ ?

$h(n) = \Theta(n^{3/2})$ because the sum of squares dominates over logarithmic factors
$h(n) = \Theta(n^{3/2} \log n)$ because the logarithmic term in the largest summand affects the total (correct answer)
$h(n) = \Theta(n \log n)$ because the summation limit $\sqrt{n}$ reduces the polynomial degree
$h(n) = \Theta(n^{3/2} \log n)$ because integration approximation includes the logarithmic factor throughout

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

Question 5

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

$f_3(n) = \Theta(n^{1 + \log_3 2})$ because logarithmic bases convert multiplicatively in products (correct answer)
$f_3(n) = \Theta(n^{\log_3 2 + \log_2 n})$ because exponents add when multiplying exponential functions
$f_3(n) = \Theta(n^{\log_3 4})$ because the product combines the logarithmic relationships asymptotically
$f_3(n) = \Theta(n^{2\log_3 2})$ because $f_2(n)$ contributes an additional factor of $\log_3 2$

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

Question 6

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?

$f(n) = O(n^2)$ but $f(n) \neq \Theta(n^2)$
$f(n) = \Theta(n^2 \log n)$ and $f(n) = O(n^3)$ (correct answer)
$f(n) = \Omega(n^2 \log n)$ but $f(n) \neq O(n^2 \log n)$
$f(n) = \Theta(n^2)$ and $f(n) = \Omega(n^2 \log n)$

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

Question 7

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

$h(n) = O(n^3)$ because $O(n^2) \cdot \Omega(n \log n) = O(n^3)$
$h(n) = O(n^3 \log n)$ because we multiply the worst-case bounds
$h(n) = O(n^2 \log n)$ because the lower bound $\Omega$ becomes irrelevant
No finite upper bound can be guaranteed without more information about the functions (correct answer)

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

Question 8

Which of the following statements about the function $f(n) = n^{\log n}$ is correct?

$f(n) = O(n^k)$ for any constant $k > 0$ since logarithms grow slowly
$f(n) = \Theta(2^{(\log n)^2})$ because $n^{\log n} = 2^{\log n \cdot \log n}$
$f(n) = \omega(n^k)$ for any constant $k$ but $f(n) = o(2^n)$ (correct answer)
$f(n) = \Theta(n!)$ because both grow super-polynomially but sub-exponentially

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

Question 9

Let $f(n) = n!$ and $g(n) = n^n$ . Which statement correctly compares their asymptotic growth rates?

$f(n) = O(g(n))$ because factorials grow slower than exponential functions
$f(n) = \Theta(g(n))$ by Stirling's approximation since both are super-exponential
$g(n) = O(f(n))$ because $n^n$ has fewer terms than $n!$
$f(n) = O(g(n))$ and $g(n) \neq O(f(n))$ because $n^n$ grows faster (correct answer)

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

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

$T(n) = \Theta(n^{\log_2 3})$ because $n^2$ dominates $n^{\log_2 3}$
$T(n) = \Theta(n^2)$ because $n^2$ dominates $n^{\log_2 3}$ (correct answer)
$T(n) = \Theta(n^2 \log n)$ because the costs are balanced at each level
$T(n) = \Theta(n^{\log_2 3} \log n)$ because $f(n) = n^{\log_2 3}$

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