Asymptotic Notations

Types of Asymptotic Notations

You may have noticed in the article that I have used only Big O notation to represent the complexities. 

So, is that the only kind of asymptotic notation?

1. Big-O Notation (O-Notation)

Big O notation represents the worst-case complexity of an algorithm. In other words, it provides an upper bound on the complexity of an algorithm. It is defined as:

O(g(n)) = f(n), such that there 0 ≤ f(n) ≤ c.g(n) for all n ≥ n₀, where c and n₀ are positive constants. This function is represented graphically as follows:

As you can see from the graph, f(n) does not exceed c.g(n) for any value of n≥ n₀. Therefore, the complexity is defined such that it has an upper bound. 

Big O Notation Examples

Before considering the example of an algorithm, let’s consider a general example. If I have ten candies in my pocket, I can say that I have less than 100 candies, providing an upper bound.

In the case of, let’s say, binary search, the maximum number of iterations (worst-case scenario) will be log n, so the complexity in Big O notation is O(log n).

2. Omega Notation (Ω-Notation)

Big Ω notation is similar to Big O notation but is exactly the opposite of it. It represents the best-case complexity of an algorithm, thereby providing a lower bound to the complexity. It is defined as follows:

Ω(g(n)) = f(n), such that there 0 ≤ c.g(n) ≤ f(n) for all n ≥ n₀, where c and n₀ are positive constants.

In the graph above, the complexity f(n) is not less than c.g(n) for any value of n ≥ n₀. Therefore, the complexity is defined with a lower bound. 

Big – omega Notation Examples

According to Big Ω notation, if I have ten candies in my pocket, I can always say I have more than one candy. 

Considering binary search again, the complexity can never be less than the best-case complexity; therefore, the complexity in Big Ω notation will be Ω(1).  In fact, the complexity in Big Ω for all algorithms is usually always Ω(1).

3. Theta Notation (Θ-Notation)

The last case of complexity we will discuss is an average-case complexity denoted by Big Θ notation. So, you can guess, It gives an upper and a lower bound to the complexity of an algorithm. 

Mathematically, it is represented as follows:

Θ(g(n)) = f(n), such that there 0 ≤ c₁.g(n) ≤ f(n) ≤ c₂.g(n) for all n ≥ n₀, where c₁, c₂ and n₀ are positive constants.

Graphically, the function is:

It is evident from the graph that the complexity f(n) is bound by an upper limit c₂.g(n) and a lower limit c₁.g(n). 

Big – Theta Notation Examples

In Big Θ notation, if I have ten candies in my pocket, I can say I have less than 100 candies, but more than one candy. 

Let us now consider a code snippet:

void print(int arr[], int n)
{
	for(int i=0;i<n;i++)
	{
    	     cout<<arr[i]<<" ";
	}
}

 

The for loop in this function will run at least n times, but it will also run a maximum of n times.

It is like saying a ≤ b and b ≤ a, which implies that a = b (here, a and b are two numbers). Therefore, Big-Theta is either the algorithm’s exact performance value or a good range between narrow upper and lower bounds.

Now that we know the different kinds of asymptotic notations, let us see the differences between them at a glance.

Properties of Asymptotic Notations

Some of the properties of asymptotic notations are:

Symmetric

If f(n) equals theta(g(n), then g(n) equals theta(f(n)).

Transpose symmetric

If f(n) equals Big-Oh(g(n)), then g(n) equals Omega(f(n)).

Transitive

If f(n) equals Big-Oh(g(n)) and g(n) equals Big-Oh(h(n)), then f(n)=Big-oh(h(n)).

Reflexive

If f(n) is given, it means f(n) is Big-Oh(f(n)).

Functions in Asymptotic Notations

There are many functions in asymptotic notations. Let us understand them by considering a simple example.  

Suppose a boy has lost his glasses somewhere in his classroom. Now, to find it, he wants to ask his classmates. We will consider different methods to find the glasses, from which we’ll get to know about the various functions in asymptotic notations. 

Note: Although all the functions are mentioned in the Big O notation (to consider the worst-case scenario), they exist in the other notations too. 

O(1)

Suppose the boy asked his friend who was sitting next to him and found his glasses. This would be the best-case scenario since he had to ask only one person.

O(n)

Suppose the boy asked every other student in the class about his glasses. If the number of students in his class is n, he would have to ask n times, and hence the complexity is a function of O(n).

O(n²)

Suppose the boy asks each of his classmates and then asks them to ask the other classmates too. Then each student would ask n times, and there are n students in all. So, the complexity will be a function of O(n²).

O(log n)

Suppose the boy divided the class into two halves depending on their seating arrangement. He asks each half whether they have seen his glasses. If one of the groups says yes, he divides that group into two halves again and continues the process until he finds his glasses. The strength of the class is n. On dividing by 2, let’s say, m times until the value becomes 1.

So,

Therefore, the complexity here is a function of O(log n).

O(n!)

Suppose the boy asked all his classmates to stand in a line facing the front of the classroom. Now, each person can ask everybody standing behind them about the glasses, but not anyone standing in front of them. So, the person at the front of the line will ask n number of people standing behind him. The second person will ask (n-1) people standing behind him, and it goes on like this. 

So, the maximum number of times asked will be:

n(n-1)(n-2)(n-3)(n-4)….(1) = n!

Therefore, the complexity here will be a function of O(n!). The graph below shows the variation of the different functions of complexity with a varying number of items. 

As you can see, O(1) has the minimum complexity and is the best-case scenario, while O(n!) happens to be the most complex. 

The functions mentioned above are most commonly encountered while calculating the complexity.

Apart from these, there is also a linear log function (NlogN), exponential function (2ⁿ), cubic function (n³), and the list is endless.

Why is Asymptotic Notation Important?

Asymptotic Notation is a very important part involved in algorithm design and analysis. Some of the main reasons of importance include:

• Comparing Efficiency - We can easily compare the efficiency of the algorithms by analyzing their average, best, and worst-case complexities.
   
• Problem-Solving - Time and Space complexities are a very important part of problem-solving in computer science. These notations help the programmer predict the program's expected time and space requirements.
   
• Standardization - Asymptotic notation provides the users with a standardized way to differentiate between multiple algorithms for the same task.
   
• Optimization - We can also use the asymptotic notations to analyze our program and further optimize it for better performance.
   
• Scaling - Asymptotic Notation also helps us check whether our algorithm can work efficiently on larger datasets.

Which asymptotic notation is best?

The best asymptotic notation depends on the context, but Big-O notation (O) is most commonly used. Big-O provides an upper bound on the growth rate of an algorithm's time or space complexity, making it useful for worst-case analysis. It helps compare algorithms by focusing on their efficiency and scalability, ignoring constant factors and lower-order terms to highlight their behavior as input size increases.

Difference between Big O, Big Omega, and Big Theta Asymptotic Notations

Parameters	Big O	Big Omega	Big Theta
Definition	It gives the worst-case complexity.	It gives the best-case complexity.	It gives the average-case complexity.
Actual Complexity	The actual complexity must be less than the Big O complexity.	The actual complexity must be more than the Big Ω complexity.	The actual complexity is often the Big Θ complexity.
Bound	It provides an upper bound.	It provides a lower bound.	It provides both an upper and a lower bound.
Representation	It is mathematically represented as:O(g(n)) = f(n), such that there 0 ≤ f(n) ≤ c.g(n) for all n ≥ n0, where c and n0 are positive constants.	It is mathematically represented as:Ω(g(n)) = f(n), such that there 0 ≤ c.g(n) ≤ f(n) for all n ≥ n0, where c and n0 are positive constants.	It is mathematically represented as:Θ(g(n)) = f(n), such that there 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n) for all n ≥ n0, where c1, c2 and n0 are positive constants.

Frequently Asked Questions

What is big-O Big Theta and Big Omega?

Big-O notation (O) describes the upper bound of an algorithm's time complexity. Big Omega (Ω) denotes the lower bound, representing the best-case scenario. Big Theta (Θ) signifies tight asymptotic bounds, indicating both upper and lower limits, thus precisely describing an algorithm's time complexity.

Why are asymptotic notations called so?

The asymptotic notations are so named because they study algorithm behavior as the input size approaches infinity. They are more concerned with the algorithm's performance increase rate than with its execution time or the space utilization.

What is asymptotic analysis of an algorithm?

An algorithm's asymptotic analysis plays a role in defining the mathematical foundation of its run-time performance. We can calculate the best-case, the average-case, and the worst-case situations of an algorithm with the help of the asymptotic analysis.

What is the Omega notation in DAA?

The omega notation () in DAA is a theoretical measure of an algorithm's performance. We use big-notation for asymptotic lower bounds since it limits the growth of the running time from below for large enough input sizes.

What is Big O notation in algorithm?

It represents an algorithm's worst-case complexity. It uses algebraic terms to characterize the difficulty of an algorithm. It defines the runtime required to execute an algorithm by identifying how the performance of the program changes as the input size grows.

How many types of Big O notations are there?

Big O notation generally includes several types reflecting algorithm efficiency: O(1) for constant time, O(log n) for logarithmic, O(n) for linear, O(n log n) for log-linear, O(n^2) for quadratic, and O(n^k) and O(2^n) for polynomial and exponential complexities, respectively.

Conclusion

In this article, we learned what asymptotic notations are, their different types and how to calculate them. Asymptotic notations are crucial for analyzing and comparing algorithm efficiency. They simplifies understanding of how algorithms scale with input size, guiding developers in choosing optimal solutions. By abstracting constant factors, it highlights the core performance characteristics, essential for efficient software development.

Recommended Reading:

• Data Structures and Algorithms
• Sorting in Data Structure
• Time Complexity of Sorting Algorithms
• Application of Graph in Data Structure
   

Happy Learning!