Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Asymptotic Notation is an important part of algorithm design and analysis in computer science. It is used to measure the efficiency and performance of various algorithms based on time and space used. Asymptotic Notation helps to differentiate between various options of algorithms and choose the algorithm that best suits our requirements.

In this blog, we will discuss Asymptotic Notations in detail. We will discuss the types of Asymptotic Notations and briefly discuss about each of them. We will also see the major differences between each of them and conclude with some briefly asked questions.

What are Asymptotic Notations?

Asymptotic Notations are mathematical notations used in algorithm analysis to describe the efficiency of algorithms based on the time and space concerning the input size. These notations provide information about the performance and scalability of the algorithm. These notations are also useful in comparing multiple algorithms and choosing the best one among all the choices.

In the next section, we will look at these notations in more detail.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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_{0}, where c and n_{0} 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_{0}. 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).

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_{1}.g(n) â‰¤ f(n) â‰¤ c_{2}.g(n) for all n â‰¥ n_{0}, where c_{1}, c_{2} and n_{0} 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_{2}.g(n) and a lower limit c_{1}.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.

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^{2})

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^{2}).

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^{n}), cubic function (n^{3}), 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:

ComparingEfficiency - 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.

What is the difference between Big O, Big Omega, and Big Theta Asymptotic Notations?

Big O

Big Omega

Big Theta

It gives the worst-case complexity.

It gives the best-case complexity.

It gives the average-case complexity.

The actual complexity must be less than the Big O complexity.

The actual complexity is often the Big Î˜ complexity.

It provides an upper bound.

It provides a lower bound.

It provides both an upper and a lower bound.

It is mathematically represented as:O(g(n)) = f(n), such that there 0 â‰¤ f(n) â‰¤ c.g(n) for all n â‰¥ n_{0}, where c and n_{0} are positive constants.

It is mathematically represented as:Î˜(g(n)) = f(n), such that there 0 â‰¤ c_{1}.g(n) â‰¤ f(n) â‰¤ c_{2}.g(n) for all n â‰¥ n_{0}, where c_{1}, c_{2} and n_{0} are positive constants.

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.

Conclusion

In this article, we learned what asymptotic notations are, their different types and how to calculate them. We also saw various functions used to express the complexity.

Now that we know how to analyze the complexity of an algorithm mathematically, we can easily compare algorithms and choose the best one. It will help us assimilate good coding practice.