**Heads up!** To view this whole video, sign in with your Courses account or enroll in your free 7-day trial.
Sign In
Enroll

Start a free Courses trial

to watch this video

Let's wrap up the course by looking at the Big O runtimes for Linear Search and Binary Search.

#### Quicksort Run Time (Worst Case)

O(n²)

#### Quicksort Run Time (Average Case)

O(n log n)

#### Merge Sort Run Time

O(n log n)

#### Linear Search Run Time

O(n)

#### Binary Search Run Time

O(log n)

#### Learning More

Let's wrap up the course by looking at the Big O run times for linear search and 0:00 binary search. 0:04 These are going to be much simpler to calculate than the sorting 0:05 algorithms were. 0:08 For linear search, you need to do one comparison to the target value for 0:10 each item in the list. 0:13 Again, theoretically, 0:15 we could find the target value before searching the whole list. 0:16 But Big O notation is only concerned with the worst case, 0:19 where we have to search the entire list. 0:22 So for a list of eight items, that means eight operations. 0:24 The Big O run time for linear search is O(n), 0:29 where n is the number of items we're searching through. 0:32 This is also known as linear time. 0:35 Because when the number of items and 0:37 number of operations are compared on a graph, the result is a straight line. 0:39 Linear search looks pretty good, until you compare it to binary search. 0:43 For binary search, the number of items you have to search through, and therefore, 0:47 the number of operations, is cut in half with each comparison. 0:52 Remember, the number of times you can divide n by two until you reach one is 0:55 expressed as log n. 1:00 So the run time of binary search in Big O notation is O(log n). 1:01 Even for very large values event, that is very large lists you have to search 1:06 through, the number of operations needed to search is very small. 1:10 Binary search is a very fast, efficient algorithm. 1:14 That's our tour of sorting and searching algorithms. 1:18 Be sure to check the teacher's notes for opportunities to learn more. 1:21 Thanks for watching. 1:25

You need to sign up for Treehouse in order to download course files.

Sign up