Theta Notation

Example

Let's consider the following three functions:

$$f ( n ) = n^2 + 2$$

$$f ( n ) = 2n^2 - 1$$

$$f ( n ) = 2n^2 + 4$$

The table below shows how these functions grow as the value of n grows from 0 and onwards. Note that we aren't considering negative values for n, but we'll explain why shortly.

f ( n )	n2 + 2	2n2 - 1	2n2 + 4
f ( 0 )	2	-1	4
f ( 1 )	3	1	6
f ( 2 )	6	7	12
f ( 3 )	11	17	22
f ( 4 )	18	31	36
f ( 5 )	27	49	54
f ( 6 )	38	71	76
f ( 7 )	51	97	102
f ( 8 )	66	127	132
f ( 9 )	83	161	166
f ( 10 )	102	199	204

We can observe from the output that the function f(n) = 2n² - 1 grows faster than the function f(n) = n² + 2, but it grows slower than f(n) = 2n² + 4 once n becomes greater than or equal to 2. The astute reader would notice that the output of the function f(n) = 2n² is, in a sense, being sandwiched by the output of the other two functions when n ≥ 2. All the yellow rows in the above table, show the values of the function f(n) = 2n² - 1 being sandwiched by the output of the other two functions.

Formal Definition

Whenever we can bound the output of a function f(n) by the ...