BrainTok
ENESIT

Data Structures and Algorithms: Asymptotic analysis and Big-O notation · Big-O, Big-Omega and Big-Theta

How O, Ω and Θ bound an algorithm's growth, and how to apply them to loops, recursion and real comparisons.

Data Structures and Algorithms · 30 questions

Try 3 questions

1. Formally, what does it mean that an algorithm's running time is O(n²)?

  1. For large n, it grows at most like n²
  2. For large n, it grows at least like n²
  3. For every n, it is exactly proportional to n²
Show the answer

Answer: For large n, it grows at most like n²

Big-O is an upper bound: there are constants c and n₀ such that the time is at most c·n² for every n ≥ n₀.

2. Which asymptotic notation expresses a lower bound on how fast a function grows?

  1. Little-o (o)
  2. Big-Omega (Ω)
  3. Big-Theta (Θ)
Show the answer

Answer: Big-Omega (Ω)

f is Ω(g) when, for large n, f(n) ≥ c·g(n) for some positive constant c: f grows at least as fast as g.

3. When is a function Θ(n log n)?

  1. When it equals n log n plus a constant
  2. When n log n bounds it from above only
  3. When n log n bounds it above and below
Show the answer

Answer: When n log n bounds it above and below

Θ is a tight bound: the function is both O(n log n) and Ω(n log n), so it is squeezed between two constant multiples of n log n.

The rest of the quiz, a few questions at a time

BrainTok asks a few questions from quizzes like these before the apps you choose open, so your screen time turns into learning. For iPhone.

Join the beta

More Computer Science quizzes