What Are Big O, Big Omega, and Theta Notations?

TL;DR

Asymptotic notations are the mathematical way of representing time complexity without executing an algorithm. Big O gives the least upper bound (at most, worst case), Big Omega gives the greatest lower bound (at least, best case), and Theta bounds a function from both sides for the average case. For f(n) = 2n^2 + n, all three resolve to n^2.

Transcript

Hello friends, welcome to Gate Smashers In this video we are going to discuss about asymptotic notations And this is one of the most important topics of the algorithm Because we discuss asymptotic notations in the syllabus So guys in this video we are going to discuss all the important points from the basics Which will be very beneficial for your ... Read More

Key Insights

• Asymptotic notation is the mathematical way of representing time complexity. It supports prior analysis, where an algorithm is analyzed without execution, by counting how many times a statement runs (iteration or frequency) or how many times a function calls itself.
• The purpose of notations is comparison. By representing one algorithm as having a certain time complexity and another as having a different one, the two can be compared directly so the better algorithm can be identified without running either.
• Big O notation represents the upper bound, also called at most, meaning the maximum time a task will take. Formally f(n) = O(g(n)) holds when f(n) is less than or equal to c.g(n), for a constant c greater than 0 and all n greater than or equal to k.
• Big O requires the least upper bound, not just any larger function. For 2n^2 + n, the terms n^2, n^3, n^4, n^5, 2^n, and n^n are all valid upper bounds mathematically, but only the closest one, n^2, is chosen.
• The dominating term decides the complexity class. In 2n^2 + n, n^2 is quadratic and n is linear, and at n = 100 the linear term is 100 while the quadratic term is 10,000, so n^2 dominates for large inputs even though small values of n show little difference.
• For f(n) = 2n^2 + n written as O(n^2), c = 2 fails because the extra plus n term breaks the inequality, so c = 3 is chosen. Solving 2n^2 + n <= 3n^2 gives n <= 2n^2, then 1 <= n, so the condition holds for all n greater than or equal to 1.
• Big Omega represents the lower bound, also called at least, and requires the greatest lower bound. For 2n^2 + n, candidates such as n^2, n, log n, and log of log n are all smaller, but the nearest one, n^2, is chosen, with c = 2 and n greater than or equal to 0.
• Theta notation bounds a function from both sides and represents the average case. For f(n) = 2n^2 + n with g(n) = n^2, c1 = 2 and c2 = 3, so 2n^2 + n is always greater than 2n^2 and always less than 3n^2.
• Big O is the notation most commonly used in practice because it reports the maximum time, which automatically covers the best case and average case within it. That is also why most complexity results are stated in terms of Big O.
• Little o differs from Big O by removing equality. Where Big O uses less than or equal to, in little o the equal to part does not apply, which is what separates it from the big notation.

Questions & Answers

Q: What is asymptotic notation in algorithms?

Asymptotic notation is the mathematical way of representing the time complexity of an algorithm. It belongs to prior analysis, which means the analysis is done without executing the algorithm. Instead of timing a run, you count how many times a statement is executed, referred to as iteration or frequency, or how many times a function calls itself. Those counts need a formal representation so that one algorithm can be stated as having a certain time complexity and another a different one, allowing the two to be compared so the better algorithm can be identified. The main notations are Big O, Big Omega, and Theta, with little o and little omega as additional ones.

Q: What is Big O notation and what does it represent?

Big O notation represents the upper bound of a function, which is also described as at most, meaning the maximum time a task will take. Writing f(n) = O(g(n)) means f(n) is always less than or equal to c.g(n), where c is a constant term that must be greater than 0, and the input value n must be greater than or equal to k, where k is greater than or equal to 0. Before the value k, the function may fluctuate, getting smaller or bigger, but after k the bounding condition holds consistently. Big O is used most often because notations are usually given in terms of Big O.

Q: How do you prove that 2n^2 + n is O(n^2)?

Start from the definition: 2n^2 + n must be less than or equal to c.n^2. Choosing c = 2 does not work, because that gives 2n^2 + n <= 2n^2, which fails since the extra plus n term is still present. Choosing c = 3 gives 2n^2 + n <= 3n^2. Solving this leaves n <= 2n^2, and dividing both sides by n gives 1 <= n, which can be written as n greater than or equal to 1. So with c = 3 and for all n greater than or equal to 1, the condition holds. Checking with n = 5: the left side is 2 times 25 plus 5, which is 55, and the right side is 3 times 25, which is 75, so 55 is less than or equal to 75.

Q: Why is n^2 chosen instead of n^3 or 2^n as the Big O of 2n^2 + n?

Mathematically, n^2, n^3, n^4, n^5, 2^n, and n^n are all larger than 2n^2 + n, so any of them technically bounds the function from above. But when talking about an upper bound in Big O, the rule is to take the least upper bound, meaning the closest larger value rather than any larger value. Among the candidates, n^2 is the closest one to 2n^2 + n, so n^2 is chosen. The same principle applies in reverse to Big Omega, where the greatest lower bound is taken, illustrated by the idea that among values smaller than 5 you take 4, the closest one, rather than 1 or 0.

Q: Why does n^2 dominate n in a time complexity expression?

In the expression 2n^2 + n, n^2 is a quadratic function and n is a linear equation, and the quadratic term dominates as the input grows. Substituting n = 100 gives a linear term of 100 while the quadratic term is 10,000. Substituting n = 1 crore gives a linear term of 1 crore while the quadratic term is 1 crore raised to the power 2. So the value of n^2 becomes much bigger than n. The dominance does not show up for small values, however: at n = 0 or n = 1 there is not much difference between the two terms. It is only for larger values that n^2 clearly grows faster, which is why the quadratic term determines the complexity.

Q: What is Big Omega notation and how is it different from Big O?

Big Omega represents the lower bound of a function, described as at least, meaning the minimum time a task will take, whereas Big O represents the upper bound, or at most. Writing f(n) = Omega(g(n)) means f(n) is always greater than or equal to c.g(n), so c.g(n) stays below the value of f(n). For f(n) = 2n^2 + n, candidate lower bounds include n^2, n, log n, and log of log n, but since the greatest lower bound is required, n^2 is chosen. Taking c = 2 gives 2n^2 + n greater than or equal to 2n^2, which holds because the plus n term is extra. Subtracting 2n^2 from both sides shows the condition holds for all n greater than or equal to 0.

Q: What does Theta notation mean in algorithm analysis?

Theta notation bounds a function from both sides at the same time and represents the average case time complexity. The representation requires that f(n) is greater than c1.g(n) and less than c2.g(n), so the function is sandwiched between two constant multiples of the same g(n). Applying it to f(n) = 2n^2 + n, the value of g(n) is n^2 on both sides, with c1 = 2 for the lower side and c2 = 3 for the upper side. That means 2n^2 + n is always greater than 2n^2 and always less than 3n^2. Because both constants multiply the same n^2, Theta gives a tighter description than either Big O or Big Omega alone.

Q: How do best case, worst case, and average case relate to searching a book?

Take a book with no indexing and no hashing, where you are searching for a topic by reading page by page, which is a linear search without any sorting. The best case, represented by Omega, is that you read the first page and immediately find your topic. The worst case, represented by Big O and meaning at max, is that you search one by one and find the topic on the last page, having gone through all n pages. The average case is when the topic is neither on the first page nor on the last page, so on average you move through half the pages. Big O is generally used to report complexity because the maximum time automatically includes the best case and the average case.

Summary & Key Takeaways

• Asymptotic notation is the mathematical way of representing time complexity, and it belongs to prior analysis, meaning the algorithm is analyzed without being executed. Instead of running code, you count how many times a statement is executed, called iteration or frequency, or how many times a function calls itself, then express that count with a notation.

• Big O notation represents the upper bound, also stated as at most, meaning the maximum time a task will take. Writing f(n) = O(g(n)) means f(n) is always less than or equal to c.g(n), where the constant c is greater than 0 and the input n is greater than or equal to k, with k greater than or equal to 0.

• Big Omega represents the lower bound, also stated as at least, and f(n) = Omega(g(n)) means f(n) is always greater than or equal to c.g(n). Theta bounds the function from both sides at once, requiring f(n) to be greater than c1.g(n) and less than c2.g(n), which represents the average case time complexity.

• The book search example makes the three cases concrete. With no indexing or hashing and a plain linear search, the best case is finding the topic on the first page, the worst case is finding it on the last page after checking all n pages, and the average case is moving through roughly half the pages.