If we know that algorithm X is \Theta(n) in the average case, then what can we say about its TIGHTEST upper bound?

It is O(n) in the average case.
  • It is O(n) or greater in the average case, but we don't have enough information to say more.
  • It is O(n) or less in the average case, but we don't have enough information to say more.
  • We don't have enough information to say.

What is the definition of \Theta(n)?

Being \Theta(n) means that we know a tight bound (both the upper and the lower bounds match).

If X is \Theta(n), then it is both O(n) and \Omega(n).