Recall that \Theta(n^2) means that all program inputs (beyond a certain, small size) run within a constant factor of n^2.

Theta means that the program is not growing too much slower, nor too much faster, than the claimed growth rate.

Sequential search grows much slower than n^2.