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

The output of the above program and the average number of comparisons is shown below. As the numbers indicate, the binary search is much faster and gets relatively faster as the size of the array grows. These notions of algorithm speed will be made more rigorous in the coming lessons.

Of course, theses averages do not account for missing or multiple elements. Multiple targets in the array will tend to speed up the linear search while a missing target value requires that the linear search check every element. Neither circumstance affects the binary search, which always requires approximately log base 2 comparisons.