**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

The algorithms we've discussed in this stage are very well-known, and some job interviewers are going to expect you to know their Big O runtimes. So let's look at them!

#### Quicksort Run Time (Worst Case)

O(n²)

#### Quicksort Run Time (Average Case)

O(n log n)

#### Merge Sort Run Time

O(n log n)

We had to learn a lot of details for each algorithm we've covered in this course. 0:00 Developers who need to implement their own algorithms often need to choose 0:04 an algorithm for each and every problem they need to solve. 0:08 And they often need to discuss their decisions with other developers. 0:11 Can you imagine needing to describe all the algorithms in this same level of 0:14 detail all the time? 0:19 You'd spend all your time in meetings rather than programming. 0:20 That's why Big O Notation was created, as a way of quickly describing how 0:24 an algorithm performs as the data set its working on increases in size. 0:28 Big O Notation lets you quickly compare several algorithms to choose the best one 0:33 for your problem. 0:37 The algorithms we've discussed in this course are very well-known. 0:39 Some job interviewers are going to expect you to know their Big O runtimes. 0:42 So let's look at them. 0:46 Remember that the n in Big O Notation refers to the number of elements you're 0:48 operating on. 0:52 With selection sort, you need to check each item on the list to see if it's 0:53 lowest so you can move it over to the sorted list. 0:57 So that's n operations. 0:59 Suppose you're doing selection sort on a list of 5 items, and 1:02 in this case, would be 5. 1:06 So that's 5 operations before you can move an item to the sorted list. 1:08 But with selection sort, you have to loop over the entire list for 1:11 each item you want to move. 1:15 There are 5 items in the list, and you have to do 5 comparisons to move each one. 1:17 So it's more like 5 times 5 operations, or 1:21 if we replace 5 with n, it's n times n, or n squared. 1:25 But wait, you might say, half of that 5 by 5 grid of operations is missing, 1:30 because we're testing one few item in the unsorted list with each pass. 1:34 So isn't it more like, 1/2 times n times n? 1:38 And this is true, we are not doing a full n squared of operations. 1:42 But remember, in Big O Notation, 1:46 as the value of n gets really big, constants like 1/2 become insignificant. 1:48 And so we discard them. 1:53 The Big O runtime of selection sort is widely recognized as being O(n squared). 1:55 Quicksort requires one operation for each element of listed sorting. 2:02 It needs to select a pivot first, and then it needs to sort elements into lists that 2:06 are less than or greater than the pivot. 2:10 So that's n operations. 2:12 To put that another way, if you have a list of 8 items, then n is 8. 2:14 So it will take 8 operations to split the list around the pivot. 2:18 But of course, the list isn't sorted after splitting it around the pivot just once. 2:22 You have to repeat those data operations several times. 2:26 In the best case you'll pick a pivot that's right in the middle of the lists, 2:29 so that you're dividing list exactly in half. 2:33 Then you keep dividing the list in half until you 2:36 have a list with a length of one. 2:38 The number of times you need to divide n in half until 2:40 you reach one is expressed as log n. 2:44 So you need to repeat n sorting up rations log n times. 2:47 That leaves us with the best case one times for Quicksort of O (n log n). 2:51 But that's the best case. 2:57 What about the worst case? 2:59 Well, if you pick the wrong pivot, 3:00 you won't be dividing the list exactly in half. 3:02 If you pick a really bad pivot, 3:04 the next recursive call to Quicksort will only reduce the list length by 1. 3:06 Since our Quicksort function simply picks the first item to use as a pivot, 3:10 we can make it pick the worst possible pivot repeatedly, 3:14 simply by giving it a list that's sorted in reverse order. 3:18 If we pick the worst possible pivot every time, we'll have to split the list once 3:21 for every item it contains, and then, do n-sorting operations on it. 3:26 You already know another sorting algorithm that only manages to reduce the list by 3:30 one element with each pass, selection sort. 3:35 Selection sort has a runtime of O(n squared). 3:37 And in the worst case, that's the runtime for Quicksort as well. 3:40 So which do we consider when trying to decide whether to use Quicksort, 3:44 the best case or the worst case? 3:48 Well, as long as your implementation doesn't just pick the first item as 3:50 a pivot, which we did so we could demonstrate this issue, 3:54 it turns out that on average, Quicksort performs closer to the best case. 3:57 Many Quicksort implementations accomplish this simply by picking a pivot at random 4:01 on each recursive loop. 4:06 Here we are sorting our reverse sorted data again, but this time we picked pivots 4:08 at random, which reduces the number of recursive operations needed. 4:12 Sure, random pivots sometimes give you the best case and 4:17 sometimes you'll randomly get the worst case. 4:19 But it all averages out over multiple calls to the Quicksort function. 4:21 Now, with Merge Sort, there is no pivot to pick. 4:26 Your list of n items always gets divided in half log n times. 4:28 That means, Merge Sort always has a big O runtime of O(n log n). 4:33 Contrast that with Quicksort, 4:38 which only has a runtime of O(n log n) in the best case. 4:40 In the worst case, Quicksort's runtime is O(n squared). 4:43 And yet, out in the real world, Quicksort is more commonly used than Merge Sort. 4:47 Now, why is that if Quicksort's bigger runtime can sometimes be worse than 4:51 Merge Sort? 4:55 This is one of those situations where Big O Notation doesn't tell you 4:56 the whole story. 5:00 All Big O can tell you is the number of times an operation is performed. 5:01 It doesn't describe how long that operation takes. 5:05 And the operation merge of performance repeatedly, 5:08 takes longer than the operation Quicksort performance repeatedly. 5:11 Big O is a useful tool for quickly describing how the runtime 5:15 of an algorithm increases as the data set it's operating on gets really, really big. 5:18 But you can't always choose between two algorithms based just on their Big O 5:23 runtimes. 5:27 Sometimes there is additional info you need to know about an algorithm 5:28 to make a good decision. 5:31 Now that we can sort a list of items, 5:33 we're well on our way to being able to search a list efficiently as well. 5:35 We'll look at how to do that in the next stage. 5:39

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

Sign up