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

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

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?

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

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

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

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

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