C++ Data Structures and Algorithms

Big Theta, Big-O, and Big Omega

After discussing asymptotic analysis and the three cases in algorithms, let's discuss asymptotic notation to represent the time complexity of an algorithm. There are three asymptotic notations that are mostly used in an algorithm; they are Big Theta, Big-O, and Big Omega.

The Big Theta notation (θ) is a notation that bounds a function from above and below, like we saw previously in asymptotic analysis, which also omits a constant from a notation. 

Suppose we have a function with time complexity 4n + 1. Since it's a linear function, we can notate it like in the following code:

f(n) = 4n + 1

Now, suppose we have a function, g(n), where f(n) is the Big-Theta of g(n) if the value, f(n), is always between c1*g(n) (lower ...