Algorithms: Big O, Big Omega, and Big Theta Notation

Big O, Big Omega, and Big Theta Notation

In this algorithms video, we lay the groundwork for the analysis of algorithms in future video lessons. Algorithmic analysis is performed by finding and proving asymptotic bounds on the rate of growth in the number of operations used and the memory consumed. The operations and memory usage correspond to the analysis of the running time and space, respectively. Since most algorithmic analysis focuses on analyzing time, we will focus on our attention on that, initially, as well.

The three types of bounds that we defined in this lesson originated from mathematics: big O, big omega, and big theta. In the video, we gave two definitions for each of these: one for real functions and one for integer functions. Since real functions are more commonly used, we gave first our definitions and corresponding graphs using real functions rather than the more appropriate integer functions. In actual practice, algorithms will take only integer input sizes.

When analyzing algorithms, the f(n) that we used will correspond to the number of operations used in the algorithms, and n will refer to the input size. The input size for an algorithm that sorts an array, for example, is the size of the array. The function g(n) corresponds to some simpler function that we can use to bound f(n). For example, we might have f(n) = 3n² +10n + 4 and g(n) = n².