Big-Theta Notation

Corresponds to the Average Case running time.

Hint

Big-Theta can be thought of as an or comparison. In other words the average case running time will always be close to or equal to the real running time averaged across all inputs.