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

?Let me start by describing the asymptotic running time.

When we study algorithms, we are interested in characterizing them according to their efficiency.

? We are usually interested in the order of growth of the running time of an algorithm, not in the exact running time. This is also referred to as the asymptotic running time.

? We need to develop a way to talk about the rate of growth of functions so that we can compare algorithms.

? Asymptotic notation gives us a method for classifying functions according to their rate of growth.??(Cusack, 2023)

We'll Compare three forms of asymptotic notation: big-Θ\Theta notation, big-O notation, and big-Ω\Omega notation.

Big – Θ (Big Theta)

Definition: Let g and f be the function from the set of natural numbers to itself. The function f is said to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0

Mathematical Representation:

Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0}

Note: Θ(g) is a set

In simple language, Big – Theta(Θ) notation specifies asymptotic bounds (both upper and lower) for a function f(n) and provides the average time complexity of an algorithm.?(UtkarshPandey6, 2023)

When we use big-Θ notation, we're saying that we have an asymptotically tight bound on the running time. "Asymptotically" because it matters for only large values of nn. "Tight bound" because we've nailed the running time to within a constant factor above and below.

?(Cormen, n.d.)

Big – ? (Big- Omega)

Definition: Let g and f be the function from the set of natural numbers to itself. The function f is said to be ?(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for all n ≥ n0

?Mathematical Representation:

?Ω(g) = {f(n): there exist positive constants c and n0 such that 0 ≤ c*g(n) ≤ f(n) for all n ≥ n0}

Note: Ω (g) is a set

In simple language, Big – Omega (?) notation specifies the asymptotic (at the extreme) lower bound for a function f(n).?(UtkarshPandey6, 2023)

We say that the running time is "big-Ω of f(n)f, left parenthesis, n, right parenthesis." We use big-Ω notation for asymptotic lower bounds since it bounds the growth of the running time from below for large enough input sizes.

(Cormen, n.d.)

Big-O analysis

Definition: Let g and f be functions from the set of natural numbers to itself. The function f is said to be O(g) (read big-oh of g), if there is a constant c > 0 and a natural number n0 such that f(n) ≤ cg(n) for all n ≥ n0.

?Note: O(g) is a set!??(UtkarshPandey6, 2023)

Abuse of notation: f = O(g) does not mean f ∈ O(g).

The Big-O Asymptotic Notation gives us the Upper Bound Idea, mathematically described below:

f(n) = O(g(n)) if there exists a positive integer n0 and a positive constant c, such that f(n)≤c.g(n) ? n≥n0

We say that the running time is "big-O of f(n)f, left parenthesis, n, right parenthesis" or just "O of f(n)f, left parenthesis, n, right parenthesis." We use the big-O notation for asymptotic upper bounds since it bounds the growth of the running time from above for large enough input sizes.

?(Cormen, n.d.)

?The difference between Big Oh, Big Omega, and Big Theta

?

?

(abhishek18bme1037, 2022)

Here are some examples to illustrate these notations:

?Example 1: Consider a simple linear search through an array of size n.

The worst-case time complexity is O(n) because it may require examining all n elements.

The best-case time complexity is Ω(1) when the target element is found in the first position.

The overall time complexity is θ(n) because it is both an upper and lower bound.

?Example 2: In the case of the bubble sort algorithm,

the worst-case and average-case time complexity is O(n^2) because it involves nested loops. However, the best-case time complexity is Ω(n) when the input is already sorted. So, bubble sort's time complexity is notated as θ(n^2) for the worst and average cases and θ(n) for the best case.

?Example 3: The merge sort algorithm consistently has a time complexity of θ(n log n) in all cases (best, worst, and average). This is because it divides the input into smaller parts and recursively sorts them, resulting in a logarithmic factor. So, its complexity is θ(n log n).(Complexity, R. o. (n.d.).)

Reference:

abhishek18bme1037. (2022). Difference between Big Oh, Big Omega, and Big Theta. Retrieved from geeks for geeks: https://www.geeksforgeeks.org/difference-between-big-oh-big-omega-and-big-theta/

Complexity, R. O. (n.d.). Asymptotic Analysis. Retrieved from Computer Science Department / Cornell University: https://www.cs.cornell.edu/courses/cs3110/2014sp/recitations/20/review-of-asymptotic-complexity.html

Cormen, T. &. (n.d.). Algorithms: Asymptotic notation. Retrieved from Khan Academy.: https://www.khanacademy.org/computing/computer-science/algorithms#asymptotic-notation

Cusack, C. A. (2023). Lecture Notes and Handouts. Retrieved from Hope College - Computer Science Dept.: https://cusack.hope.edu/Notes/Notes/Algorithms/AlgorithmAnalysis/AsymptoticNotation.pdf

UtkarshPandey6. (2023, Aug. 14). geeks for geeks. Retrieved from Analysis of Algorithms | Big – Θ (Big Theta) Notation: https://www.geeksforgeeks.org/analysis-of-algorithms-big-theta-notation/