Running time =====
Whenever the maximum amount of guesses is equal to the size of the list, we generally define this to be linear time
Whenever we want to determine how fast an algorithm is, we generally use something known as Big O Notation.
Important
That’s why it’s not enough to know how long an algorithm takes to run—you need to know how the running time increases as the list size increases.
Big O Notation tells you how fast an algorithm is. For example, let's say that you have a list of size *n.* The run time in Big O Notation is *O(n)*.
Notice that Big O Notation doesn't ask for the speed in seconds. Big O notation lets you compare the number of operations. It tells you how fast the algorithm grows.
What does that look like for Binary search? O(log_2_n)
Note: Big O Notation establishes a worst-case run time. The worst case is that you iterate through every element until you find the desired one, the worst case is that you have to apply binary search indefinitely until you find your desired element.
Here are some common Big O Run Times:
Big O Notation Known as Examples O(log_n) Log time Binary search O(n) Linear time Simple search O(n*log_n) Fast sort algorithm Quicksort O(n^2) Slow sorting algorithm Selection sort O(n!) Really slow sorting algorithm Travelling salesperson!
