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

In this video we look at how we can determine the runtime of algorithms we write

Over the last few videos, 0:00 we took a look at common complexities that we would encounter in studying algorithms. 0:01 But the question remains, 0:06 how do we determine what the worst case complexity of an algorithm is? 0:08 Earlier I mentioned that even though we say that an algorithm has 0:12 a particular upper bound or worst case run time, 0:16 each step in a given algorithm can have different run times. 0:19 [SOUND] Let's bring up the steps for binary search again. 0:22 Assuming the list is sorted, 0:26 the first step is to determine the middle position of the list. 0:28 In general, this is going to be a constant time operation. 0:32 Many programming languages hold on to information about the size of the list, so 0:35 we don't actually need to walk through the list to determine the size. 0:40 Now, if we didn't have information about the size of the list, we would need to 0:44 walk through counting each item one by one until we reach the end of the list. 0:49 And this is a linear time operation. 0:54 But realistically, this is a big O(1) or constant time. 0:57 Step 2 is to compare the element in the middle position to the target element. 1:02 We can assume that in most modern programming languages, 1:07 this is also a constant time operation because the documentation for 1:11 the language tells us it is. 1:15 Step 3 is our success case and the algorithm ends. 1:17 This is our best case, and so 1:20 far we have only incurred two constant time operations. 1:22 So we would say that the best case run time of binary search is constant time, 1:26 which is actually true. 1:31 But remember that best case is not a useful metric. 1:33 Step 4, if we don't match, is splitting the list into sublists. 1:36 Assuming the worst case scenario, 1:41 the algorithm would keep splitting into sublists 1:43 until a single element list is reached with the value that we're searching for. 1:46 The run time for 1:51 this step is logarithmic since we discard half the values each time. 1:52 So in our algorithm, we have a couple of steps that are constant time, and 1:56 one step that is logarithmic overall. 2:01 When evaluating the run time for an algorithm, we say that the algorithm has, 2:03 as its upper bound, the same run time as the least efficient step in the algorithm. 2:09 Think of it this way. 2:15 Let's say you're participating in a triathalon, 2:16 which is a race that has a swimming, running, and a cycling component. 2:19 You could be a phenomenal swimmer and a really good cyclist, but 2:23 you're a pretty terrible runner. 2:27 No matter how fast you are are at swimming or cycling, 2:29 your overall race time is going to be impacted the most by your running 2:32 race time because that's the part that takes you the longest. 2:36 If you take an hour 30 to finish the running component, 55 minutes to swim, and 2:39 38 minutes to bike, it won't matter if you can fine tune your swimming technique down 2:44 to finish in 48 minutes and your cycle time to 35, because you're still bounded 2:50 at the top by your running time, which is close to almost double your bike time. 2:55 Similarly, with the binary search algorithm, it doesn't matter how fast we 3:00 make the other steps, they are already as fast as they can be. 3:04 In the worst case scenario, the splitting of the list down to a single element list 3:08 is what will impact the overall running time of your algorithm. 3:12 This is why we say that the time complexity, or 3:16 the run time of the algorithm in the worst case is big O of log in or a logorithmic. 3:19 As I alluded to though, your algorithm may hit a best case run time, and 3:25 in between the two, best and worst case, have an average run time as well. 3:29 This is important to understand, 3:34 because algorithms don't always hit their worst case. 3:35 But this is getting a bit too complex for us. 3:38 For now, we can safely ignore average case performances and 3:40 focus only on the worst case. 3:44 In the future, if you decide to stick around, we'll circle back and 3:45 talk about this more. 3:50 Now that you know about algorithms, complexities, and big O, 3:51 let's take a break from all of that and write code in the next video. 3:55

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

Sign up