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.

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 outputs of two other functions in the following form, we say that the function f(n) belongs to the set Θ(g(n)) (pronounced as theta of g(n))

...