main resources links contact

Recitation 06

Binary Search

Counting Operations

(not covered during recitation)

For this example, we will consider the code contained in swap.c0

We first notice that the loop runs $n - 1$ times. In each iteration, we have two operations--one checking the loop condition and another incrementing $i$--in addition to the function call. Furthermore, there is one extra op that occurs once, initially setting $i = 0$. Lastly, swap() has 3 ops. Therefore, we can refer to the number of operations on an input of size $n$ as $T(n) = (n - 1)(3 + 2) + 1 = 5n - 4$.

Now, that was pretty tedious, right? Especially for any larger function, counting operations would be a nightmare. Well, does the number of ops really matter? The more important thing to take away from this is that the number of ops has some dependence on $n$. In fact, we could say that $T(n) \propto n$ ($\propto$: is proportional to). Going back to our equation before, how does the number of ops change as I change $n$? If $n = 10$ then $T(n) = 5(10) - 4 = 46$. If we increase to $n = 20$ then $T(n) = 5(20) - 4 = 96$. So, the number of operations roughly doubled, which makes sense.

Now, let's consider binary search again. In iteration of the loop, we effectively cut the number of elements between upper and lower in half each time. So, for binary search, it doesn't seem like $T(n) \propto n$, since most of the elements are never visited. It turns out that by cutting half of the remaining elements out each time, $T(n) \propto log_2 n$. Consider how this affects the total number of operations as $n$ varies for a small interval (left) and a large interval (right).


On the small interval, there is a noticeable difference, but it's not too impressive. However, on the larger interval the difference is quite dramatic. So, what can we conclude about how using linear search compares to binary search? We will continue exploring ways to analyze runtime next week.

If you have any comments or see any errors, please let me know.