Linear & Quadratic Time

Next up, 0:00 let's look at the situation we encountered with the linear search algorithm. 0:01 We saw that in the worst case scenario, whatever the value of n, 0:05 John took exactly that many tries to find the answer. 0:09 As in linear search, when the number of operations to 0:13 determine the result in the worst case scenario is at most the same as n, 0:16 we say that the algorithm runs in linear time. 0:21 We represent this as O(n). 0:24 Now, you can read that as big O of n, like I just said, or you can say linear time, 0:27 which is more common. 0:32 When we put that up on a graph against constant time and logarithmic time, 0:33 we get a line that looks like this. 0:38 Any algorithm that sequentially reads the input will have linear time. 0:40 So remember any time you know a problem involves reading every item in a list, 0:45 that means a linear runtime. 0:50 As you saw from the game we played, Britney's strategy using binary search was 0:52 clearly better, and we can see that on the graph. 0:57 So if we had the option, why would we use linear search, which runs in linear time? 0:59 Remember, that binary search had a precondition, 1:05 the inputs that had to be sorted. 1:08 While we won't be looking at sorting algorithms in this course, 1:10 as you learn more about algorithms, you'll find that sorting algorithms have varying 1:13 complexities themselves, just like search does. 1:18 So we have to do additional work prior to using binary search. 1:20 For this reason in practice linear search ends on being more peformant on 1:25 the certain value on n, Because the combination of sorting first and 1:30 then searching using binary search adds up. 1:34 The next common complexity you will hear about is when an algorithm runs in 1:37 Quadratic Time. 1:42 And the word Quadratic sounds familiar to you, 1:43 it's because you might have heard about in Math class. 1:45 Quadratic is a word that means an operation raised to the second power or 1:49 when something is squared. 1:54 Let's say you and your friends are playing a tower defense game and 1:56 to start it off you're going to draw a map of the terrain. 2:00 This map is going to be a grid and 2:03 you pick a random number to to determine how long this grid is. 2:05 Let's set n the size of the grid to 4. 2:09 [SOUND] Next, you need to come up with a list of coordinates, so 2:11 you can place towers and enemies and stuff on this map. 2:15 So, how do we do this? 2:18 If we start out horizontally, we'd have coordinate points that go (1,1), 2:20 (1,2), (1,3) and (1,4). 2:24 Then you go up one level, vertically, and we have points (2,1), (2,2), 2:27 (2,3) and (2,4). 2:32 Go up one more and you have the points (3,1), (3,2), (3,3) and (3,4). 2:33 And on that last row, you have the points (4,1), (4,2), (4,3) and (4,4). 2:38 Notice that we have a pattern here. 2:44 For each row, [SOUND] we take the value and 2:46 then create a point by adding to that every column value. 2:49 The range of values go from 1 to the value of n. 2:53 So we can generally think of it this way. 2:56 For the range of values from 1 to n, for each value in that range, we create 2:58 a point by combining that value with the range of values from 1 to n again. 3:04 Doing it this way for 3:09 each value in the range of 1 to n recreate an n number of values, 3:11 and we end up with 16 points, which is also n times n, or n squared. 3:16 This is an algorithm with a quadratic run time, because for 3:22 any given value of n, we carry out n squared number of operations. 3:26 Now, I picked a relatively easy, so to speak, example, here, 3:30 because in English, at least, we often denote map sizes by height times width. 3:34 So we would call this a four by four grid, which is just another way of saying, 3:39 four squared or n squared. 3:44 In O notation, we would write this as big O(n2), or 3:46 say that this is an algorithm with a quadratic runtime. 3:50 Many search algorithms have a worst case quadratic runtime, 3:54 which you'll learn about soon. 3:58 Now, in addition to quadratic runtimes, 4:00 you may also run into Cubic Runtimes as you encounter different algorithms. 4:02 In such an algorithm, for given value of n, 4:06 the algorithm executes n^3 number of operations. 4:10 These are as common as quadratic algorithms though, so 4:14 you won't look at any examples, but I think it's worth mentioning. 4:17 Thrown up on our graph [SOUND] quadratic in cubic run times look like this. 4:20 So this is starting to look pretty expensive computationally as they say. 4:25 We can see here that for small changes in n is a pretty significant change in 4:29 a number of operations that we need to carry out. 4:34