Theta notation

In the last article we met the second computational notation used to define the asymptotic behavior of algorithms: the Ω (Omega) notation. In this article we will teach you the third computational notation used to mathematically define the asymptotic behavior of algorithms: the Theta notation, represented by the Greek letter Θ.

If you haven’t read the article about the Ω (Omega) notation, click on this link and access the article where we explain in detail about the subject. It is highly recommended that you have some knowledge of Big O and Ω (Omega) notations before reading this article!

In the most objective way possible, the Θ (Theta) notation provides us with a simplified symbology to represent a tight performance threshold for an algorithm. An exact time limit that an algorithm takes to run.

That is, the Θ notation represents the meeting point between the Ω (lower limit) and Big O (upper limit) notations.

Formal mathematical definition

Unlike what we did for the articles on Ω and Big O notations, let’s address the mathematical definition of Θ notation before moving on to the examples.

Given two algorithm time complexity functions: f(n) and g(n). The formal mathematical definition states that:

• f(n) = Θ(g(n)) (read “f of n is Theta of g of n”) if there are two positive constants c₁ and c₂ and a value n₀, such that c₁.g(n) ≤ f(n) ≤ c₂.g(n) for all n ≥ n₀

That is, if it is bounded from above and below (at the same time) by the same function g(n).

Let’s demonstrate with some illustrated examples.

Mathematical resolution: 1st example

Let’s try to demonstrate by definition that 4n+1=Θ(n) (read “is theta of n”).

First, we have to:

• f(n) = 4n+1
• g(n) = n

If, by mathematical definition, we need to demonstrate that there are two positive constants c₁ and c₂ and an initial value n₀, so that:

• c₁.g(n) ≤ f(n) ≤ c₂.g(n) for all n ≥ n₀

So, for this problem, we need to show that:

• c₁.n ≤ 4n+1 ≤ c₂.n for all n ≥ n₀.

In summary: we need to prove that, for all values of n greater than or equal to n₀, the function 4n+1 is:

• greater than or equal to c₁ multiplied by n and;
• less than or equal to c₂ multiplied by n.

To do so, the first decision we need to make is to choose values for the constants c₁ and c₂. In this case, let’s consider c₁ being equal to the value 4 and c₂ being equal to the value 5. See below a table that shows the inequality results for some values of n:

Note that, for all values of n ≥ 1 expressed in the table above, the function of the 4n+1 algorithm is always greater than 4n and less than or equal to 5n.

When we plot a graph for both functions, we see more clearly how the function 4n+1 is bounded above by the function 5n and below by the function 4n:

This means that the 4n+1 function will never have a growth behavior smaller than 4n nor will it grow more than 5n. For this reason, we say that Θ(n) represents a tight asymptotic limit for the function 4n+1, because it is bounded above and below by two other functions of the same asymptotic class: the linear class n.

In this way, we managed to prove our objective. There are two positive constants c₁=4 and c₂=5 and a n₀=1, such that c₁.n ≤ 4n+1 ≤ c₂.n for all values of n greater than or equal to n₀.

Therefore, it is proved that, in fact, 4n+1 = Θ(n).

Mathematical resolution: 2nd example (wrong)

Let’s try to demonstrate by definition that 5n²-n+1=Θ(n) (read “is theta of n”).

First, we have to:

• f(n) = 5n²-n+1
• g(n) = n

So, for this problem, we need to show that:

• c₁.n ≤ 5n²-n+1 ≤ c₂.n for all n ≥ n₀

In summary: we need to prove that, for all values of n greater than or equal to n₀, the function 5n²-n+1 is:

• greater than or equal to c₁ multiplied by n and;
• less than or equal to c₂ multiplied by n.

To do so, the first decision we need to make is to choose values for the constants c₁ and c₂. In this case, let’s consider c₁ being equal to the value 5 and c₂ being equal to the value 10. See below a table that shows the inequality results for some values of n:

Note that, for all values of n ≤ 2 expressed in the table, the algorithm’s function 5n²-n+1 is in fact less than or equal to function 10n. However, from the value of n=3 the function 5n²-n+1 is superior to the function 10n (corrupting the rule f(n) ≤ c₂.g(n)).

This happens because the 10n function, being linear, will never be able to overcome the 5n²-n+1 function, which is quadratic.

See the relationship between the functions in the chart below. We can visualize with greater clarity how the function 5n²-n+1 manages to limit inferiorly the function 5n, for values of n ≥ 1. However, notice that the function 10n does not represent an asymptotic superior limit for the function 5n²-n+1, being surpassed by it for values of n > 2.

This means that Θ(n) does not represent a tight asymptotic limit for the function 5n²-n+1. It means that there are no positive constants c₁ and c₂ and an n₀, such that c₁.n ≤ 5n²-n+1 ≤ c₂.n for all values of n greater than or equal to n₀.

In this way, it is proved that, in fact, 5n²-n+1≠Θ(n). (reads “is not theta of n”).

Mathematical resolution: 3rd example (wrong)

Let’s try to demonstrate by definition that 4n+4=Θ(n²) (read “is theta of n”).

First, we have to:

• f(n) = 4n+4
• g(n) = n²

So, for this problem, we need to show that:

• c₁.n² ≤ 4n+4 ≤ c₂.n² for all n ≥ n₀

In summary: we need to prove that, for all values of n greater than or equal to n₀, the function 4n+4 is:

• greater than or equal to c₁ multiplied by n² and;
• less than or equal to c₂ multiplied by n².

To do so, the first decision we need to make is to choose values for the constants c₁ and c₂. In this case, let’s consider c₁ being equal to the value 1 and c₂ being equal to the value 3. See below a table that shows the inequality results for some values of n:

Note that, for all values of n ≤ 4 expressed in the table, the algorithm function 4n+4 is in fact maior ou igual to function n². However, from the value of n=5 function 4n+4 is overcome by function n² (corrupting the rule c₁.g(n) ≤ f(n)).

It turns out that the function n², being quadratic, can never be surpassed by the function 4n+4, which is linear.

See the relationship between the functions in the chart below. Notice how the 4n+4 function is overcome by the two functions (n² and 3n²) for values of n > 4.

This means that Θ(n²) does not represent a tight asymptotic limit for the 4n+4 function. It means that there are no positive constants c₁ and c₂ and a n₀, such that c₁.n² ≤ 4n+4 ≤ c₂.n² for all values of n greater than or equal to n₀.

In this way, it is proved that, in fact, 4n+4≠Θ(n²). (read “is not theta of n squared”).

Relationships between Big O, Omega and Theta notations

An easy and practical way to understand the relationship between the three asymptotic notations (Big O, Ω and Θ) is to determine the asymptotic limits of a given function by constructing what we call an asymptotic relationship table. See how it can be done.

Given a time complexity function T(n) = 4n+4, we can easily discover all its Big O, Ω and Θ relationships by building a table where the rows represent the asymptotic classes and the columns represent the notations.

Note that a function T(n) = 4n+4 is only Θ(n) (Theta of n) because it is Ω(n) (Omega of n) and O(n) (Big O of n) at the same time. That is, a function is Theta of a asymptotic class if it is Omega and Big O of that same asymptotic class!

In this way, the meaning of the asymptotic Big O, Ω and Θ notations is understood. They serve to represent performance limits of algorithms.

Tight limits and loose limits

The concepts of tight and loose limits allow us to classify the overall performance of an algorithm, taking into account its best and worst cases.

Loose asymptotic limit

When we say that algorithm A has:

• In the worst case: T(n) = 5n²-n+1
• In the best case: T(n) = 3n+2

We are claiming that:

• In the worst case: T(n) = Θ(n²) (Theta of n squared), as it has quadratic complexity
• In the best case: T(n) = Θ(n) (Theta of n), as it has linear complexity

This means that algorithm A has a loose asymptotic limit, since, in general, its performance behaves differently for the best and worst case.

That is, it, in general, is O(n²) and Ω(n).

Tight asymptotic limit

When we say that algorithm B has:

• In the worst case: T(n) = 4n+1
• In the best case: T(n) = 3n+2

We are claiming that:

• In the worst case: T(n) = Θ(n) (Theta of n), as it has linear complexity
• In the best case: T(n) = Θ(n) (Theta of n), as it has linear complexity

This means that algorithm B has a tight asymptotic limit, since, in general, their performance behaves the same for the best and worst case.

That is, it, in general, is Θ(n).

Exercises

To demonstrate that you have understood the concept and the formal mathematical definition of Theta notation well, solve the proposed exercises:

Exercises A

Try to prove mathematically that n²+800 = Θ(n²).

Try to prove mathematically that n+10 = Θ(n²).

Try to prove mathematically that 2n+10 = Θ(n).

Try to prove mathematically that 7n-2 = Θ(1).

Try to prove mathematically that n²+20n+5 = Θ(n³).

Exercise B

Complete the asymptotic relationship table below:

Exercise C

Using the instructions counting technique, find the complexity formula T(n) of the algorithm below, and then try to mathematically demonstrate that this formula found is Θ(n²).

1.public static void func(int[ ] n){
2.    for (int i=0; i<n.length-1; i++) {
3.        for (int j=0; j<n.length-1; j++) {
4.            n[j]=n[j]+(i*j);
5.        }
6.    }
7.}

And so we come to the end of the first part of the algorithm analysis course, which aimed to teach you the basics of the instructions counting technique and the 3 main asymptotic notations.

Soon we will be producing the second part of this course, aimed at teaching the techniques used for the analysis of recursive algorithms.