Asymptotic Notation Made Precise · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

What big-O really promises

Computing · Algorithms & Data Structures · ages 18-19
Name ______________________   Date ____________

  1. You already said a time is O of g. What does adding big-Omega add, and what does Theta mean?

    • Omega bounds from below, and Theta means both bounds share one g
    • Omega bounds from above, and Theta means neither bound holds
    • Omega counts exact steps, and Theta counts memory instead

  2. You claim a running time is O of g. What have you promised?

    • The time exactly equals g on every input
    • Some constant multiple of g stays above it from some size onward
    • The time stays below g divided by a constant forever

  3. Six copies of n squared stay above 5 n squared plus 30 n from some size onward. From which whole starting size does this hold?

    Answer: ______________

  4. Binary search finishes on the first guess when you are lucky. Which statement is honest?

    • It is Theta of log n because the worst case is log n
    • It is O of log n, since lucky runs beat the lower bound
    • It is Theta of 1 because the best case is constant

  5. Why is 5 n squared plus 30 n not O of n?

    • Because big-O never applies to sums of two terms
    • Because 30 is too large to serve as a constant
    • Because no constant multiple of n can contain the n squared term

  6. An O of n squared method always runs slower than an O of n method.

    Circle one:   True   False

  7. Answering needs a look at every one of n items. Which notation states that no method beats linear growth here?

    • O of n, which caps growth from above
    • Theta of 1, which promises constant time
    • Omega of n, which floors growth from below

  8. Which pair of constant and starting size makes 5 n squared plus 30 n O of n squared?

    • Constant 5 from size 1
    • Constant 6 from size 10
    • Constant 6 from size 30
LightMySky · lightmysky.comW1-mt_B0Z6Syy8Ve-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

What big-O really promises W1-mt_B0Z6Syy8Ve-s1

  1. Omega bounds from below, and Theta means both bounds share one g · Omega floors the growth, and Theta is an O plus an Omega on the same g.
  2. Some constant multiple of g stays above it from some size onward · Big-O is an upper bound with a hidden constant and a hidden starting size.
  3. 30 · 30 n fits inside n squared exactly when n reaches 30.
  4. It is O of log n, since lucky runs beat the lower bound · O allows faster lucky runs, while Theta would wrongly demand the lower bound always.
  5. Because no constant multiple of n can contain the n squared term · The squared term outgrows every straight line, whatever constant you pick.
  6. False · Hidden constants rule small inputs. Growth rates only decide the long run.
  7. Omega of n, which floors growth from below · Skipping an item means never looking at it, so linear work is the floor.
  8. Constant 6 from size 30 · Only 6 from 30 keeps 6 n squared above the function from there on.
Worksheet · LightMySky