1 00:00:00,417 --> 00:00:05,297 The runtimes we've looked at so far are all called polynomial runtimes. 2 00:00:05,297 --> 00:00:09,460 An algorithm is considered to have a polynomial run time if, for 3 00:00:09,460 --> 00:00:10,701 a given value of n. 4 00:00:10,701 --> 00:00:15,029 It's worst-case runtime is in the form of n raised to the k power, 5 00:00:15,029 --> 00:00:17,051 where k just means some value. 6 00:00:17,051 --> 00:00:21,842 So it could be n squared, where k = 2, for a quadratic runtime, and cubed for 7 00:00:21,842 --> 00:00:23,597 a cubic runtime, and so on. 8 00:00:23,597 --> 00:00:27,312 All of those are in the form of n raised to some power. 9 00:00:27,312 --> 00:00:31,190 Anything that is bounded by this, and what I mean by that is, 10 00:00:31,190 --> 00:00:35,461 if we had a hypothetical line on our graph of n raised to the k power? 11 00:00:35,461 --> 00:00:40,709 Anything that falls under this graph is considered to have a polynomial runtime. 12 00:00:40,709 --> 00:00:42,952 Algorithms with an upper bound, or 13 00:00:42,952 --> 00:00:45,941 a runtime with a big O value that is polynomial, 14 00:00:45,941 --> 00:00:50,896 are considered efficient algorithms, and are likely to be used in practice. 15 00:00:50,896 --> 00:00:55,349 Now, the next class of runtimes that we're going to look at are runtimes that we 16 00:00:55,349 --> 00:00:57,020 don't consider efficient. 17 00:00:57,020 --> 00:01:00,272 And these are called exponential runtimes. 18 00:01:00,272 --> 00:01:03,470 With these runtimes, as n increases slightly, 19 00:01:03,470 --> 00:01:06,982 the number of operations increases exponentially. 20 00:01:06,982 --> 00:01:08,834 And as we'll see in a second, 21 00:01:08,834 --> 00:01:12,027 these algorithms are far too expensive to be used. 22 00:01:12,027 --> 00:01:16,311 An exponential runtime is an algorithm with a big O value of 23 00:01:16,311 --> 00:01:19,030 some number raised to the nth power. 24 00:01:19,030 --> 00:01:23,066 Imagine that you wanted to break into a locker that had a padlock on it. 25 00:01:23,066 --> 00:01:25,028 Let's assume you for forgot your code. 26 00:01:25,028 --> 00:01:30,816 This lock takes a two-digit code, and the digit for the code ranges from 0 to 9. 27 00:01:30,816 --> 00:01:33,196 You start by setting the dials to 0. 28 00:01:33,196 --> 00:01:38,064 And then, with the first dial remaining on 0, you change the second dial to 1, 29 00:01:38,064 --> 00:01:39,288 and try and open it. 30 00:01:39,288 --> 00:01:42,191 If it doesn't work, you set it to 2, and try again. 31 00:01:42,191 --> 00:01:43,809 You would keep doing this, and 32 00:01:43,809 --> 00:01:47,116 if you still haven't succeeded with the second dial set to 9? 33 00:01:47,116 --> 00:01:52,253 Then you go back to that first dial, set it to 1, and start the second dial over. 34 00:01:52,253 --> 00:01:57,052 The range of values you'd have to go through is 0-0 to 9-9, 35 00:01:57,052 --> 00:01:58,896 which is 100 values. 36 00:01:58,896 --> 00:02:02,527 This can be generalized as 10 to the 2nd power, 37 00:02:02,527 --> 00:02:07,029 since there are 10 values on each dial, raised to 2 dials. 38 00:02:07,029 --> 00:02:11,092 Searching to each individual value, until you stumble on the right one, 39 00:02:11,092 --> 00:02:13,002 is a strategy called brute force. 40 00:02:13,002 --> 00:02:16,816 And brute force algorithms have exponential runtimes. 41 00:02:16,816 --> 00:02:20,809 Here, there are two dials, so n is 2, and each dial has 10 values. 42 00:02:20,809 --> 00:02:25,059 So again, we can generalize this algorithm as 10 raised to n, 43 00:02:25,059 --> 00:02:27,747 where n represents the number of dials. 44 00:02:27,747 --> 00:02:32,413 The reason that this algorithm is so inefficient is because with just one more 45 00:02:32,413 --> 00:02:36,742 dial on the lock, the number of operations increases significantly. 46 00:02:36,742 --> 00:02:41,184 With three dials, the number of combinations in the worst-case scenario, 47 00:02:41,184 --> 00:02:45,621 where the correct code is the last digit in the range, is 10 raised to 3, or 48 00:02:45,621 --> 00:02:46,875 1,000 values. 49 00:02:46,875 --> 00:02:51,559 With an additional wheel, it becomes 10 raised to 4, or 10,000 values. 50 00:02:51,559 --> 00:02:55,984 As n increases, the number of operations increases exponentially, 51 00:02:55,984 --> 00:03:00,034 to a point where it's unsolvable in a realistic amount of time. 52 00:03:00,034 --> 00:03:05,019 Now you might think, well, any computer can crack a four-digit numerical lock. 53 00:03:05,019 --> 00:03:08,108 And that's true, because n here is sufficiently small. 54 00:03:08,108 --> 00:03:12,108 But this is the same principle that we use for passwords. 55 00:03:12,108 --> 00:03:16,799 In a typical password field, implemented well, users are allowed to use letters of 56 00:03:16,799 --> 00:03:19,715 the English alphabet, so to up to 26 characters. 57 00:03:19,715 --> 00:03:21,533 Numbers from 0 to 9, and 58 00:03:21,533 --> 00:03:25,843 a set of special characters of which there can be around 33. 59 00:03:25,843 --> 00:03:32,099 So typically, that means each character in a password can be 1 out of 69 values. 60 00:03:32,099 --> 00:03:35,507 This means that for a one-character password, 61 00:03:35,507 --> 00:03:38,175 it takes 69 to the nth power, so 1. 62 00:03:38,175 --> 00:03:42,000 Which equals 69 operations, in the worst-case scenario, 63 00:03:42,000 --> 00:03:43,739 to figure out the password. 64 00:03:43,739 --> 00:03:49,187 Just increasing n to 2 increases the number of operations needed 65 00:03:49,187 --> 00:03:54,842 to guess the password to 69 squared, or 4,761 operations. 66 00:03:54,842 --> 00:03:58,661 Now usually, on a secure website, there isn't really a limit. 67 00:03:58,661 --> 00:04:03,665 But in general, passwords are limited to around 20 characters in length. 68 00:04:03,665 --> 00:04:08,539 With each character being a possible 69 values, and there being 20 characters. 69 00:04:08,539 --> 00:04:11,913 The number of operations needed to guess the password, 70 00:04:11,913 --> 00:04:15,950 in the worst-case scenario, is 69 raised to the 20th power. 71 00:04:15,950 --> 00:04:22,232 Or approximately 6, followed by 36 zeros, number of operations. 72 00:04:22,232 --> 00:04:26,988 An intel CPU with five cores can carry out roughly about 65,000 73 00:04:26,988 --> 00:04:29,452 million instructions per second. 74 00:04:29,452 --> 00:04:31,367 That's a funny number, I know. 75 00:04:31,367 --> 00:04:36,656 To crack our 20-digit passcode in this very simplistic model, it 76 00:04:36,656 --> 00:04:43,416 would take this Intel CPU 2 raised to 20th power years to brute-force the password. 77 00:04:43,416 --> 00:04:47,222 So while this algorithm would eventually produce a result, it is so 78 00:04:47,222 --> 00:04:49,311 inefficient that it's pointless. 79 00:04:49,311 --> 00:04:53,387 This is one of the reasons why people recommend you have longer passwords. 80 00:04:53,387 --> 00:04:56,883 Since brute forcing is exponential in the worst case, 81 00:04:56,883 --> 00:05:01,827 each character you add increases the number of combinations by an exponent. 82 00:05:01,827 --> 00:05:05,948 The next class of exponential algorithms is best highlighted 83 00:05:05,948 --> 00:05:09,523 by popular problem known as the traveling salesman. 84 00:05:09,523 --> 00:05:11,393 The problem statement goes like this. 85 00:05:11,393 --> 00:05:15,684 Given a list of cities, and the distance between each pair of cities. 86 00:05:15,684 --> 00:05:19,781 What is the shortest possible route that visits each city, and 87 00:05:19,781 --> 00:05:21,959 then returns to the origin city? 88 00:05:21,959 --> 00:05:23,887 This seems like a simple question. 89 00:05:23,887 --> 00:05:28,357 But let's start with a simple case, three cities, A, B, and C. 90 00:05:28,357 --> 00:05:30,842 To figure out what the shortest route is, 91 00:05:30,842 --> 00:05:33,685 we need to come up with all the possible routes. 92 00:05:33,685 --> 00:05:37,489 With three cities, we have 6 routes, in theory at least. 93 00:05:37,489 --> 00:05:39,092 Some of these routes can be discarded. 94 00:05:39,092 --> 00:05:43,916 Because A-B-C is the same as C-B-A, but in the opposite direction. 95 00:05:43,916 --> 00:05:45,625 But as we do know sometimes, 96 00:05:45,625 --> 00:05:50,345 going from A to C through B may go through a different route than C through A to B. 97 00:05:50,345 --> 00:05:54,934 So we'll stick to the six routes, and from there, we could determine the shortest, 98 00:05:54,934 --> 00:05:55,647 no big deal. 99 00:05:55,647 --> 00:06:00,268 Now, if we increase this to four cities, we jump to 24 combinations. 100 00:06:00,268 --> 00:06:05,047 The mathematical relationship that defines this is called a factorial, and 101 00:06:05,047 --> 00:06:08,369 is written out as n followed by an exclamation point. 102 00:06:08,369 --> 00:06:15,083 Factorials are basically n times (n- 1), repeated until you reach the number 1. 103 00:06:15,083 --> 00:06:20,610 So for example, the factorial of 3 is 3 x 2 x 1, which is 6. 104 00:06:20,610 --> 00:06:24,372 Which is the number of combinations we came up with for three cities. 105 00:06:24,372 --> 00:06:28,117 The factorial of 4 is 4 x 3 x 2 x 1, or 24, 106 00:06:28,117 --> 00:06:33,603 which is the number of combinations we arrived at with four cities. 107 00:06:33,603 --> 00:06:36,571 In solving the travelling salesman problem, 108 00:06:36,571 --> 00:06:40,535 the most efficient algorithm will have a factorial runtime. 109 00:06:40,535 --> 00:06:44,250 Or a combinatorial runtime, as it's also called. 110 00:06:44,250 --> 00:06:48,666 At low values of n, algorithms with a factorial runtime may be used. 111 00:06:48,666 --> 00:06:50,862 But with an n value of say, 200, 112 00:06:50,862 --> 00:06:55,194 it would take longer than humans have been alive to solve the problem. 113 00:06:55,194 --> 00:07:00,110 For sake of completeness, let's plot a combinatorial runtime on our graph, so 114 00:07:00,110 --> 00:07:01,422 that we can compare. 115 00:07:01,422 --> 00:07:06,302 An algorithm, such as one that solves the traveling salesman problem, 116 00:07:06,302 --> 00:07:09,664 has a worst-case runtime of big O of n factorial. 117 00:07:09,664 --> 00:07:14,012 Studying exponential runtimes like this are useful for two reasons. 118 00:07:14,012 --> 00:07:17,432 First, in studying how to make such algorithms efficient, 119 00:07:17,432 --> 00:07:20,661 we develop strategies that are useful across the board. 120 00:07:20,661 --> 00:07:25,404 And can potentially be used to make existing algorithms even more efficient. 121 00:07:25,404 --> 00:07:29,658 Second, it's important to be aware of problems that take a long time to solve. 122 00:07:29,658 --> 00:07:34,246 Knowing right off the bat that a problem is somewhat unsolveable in a realistic 123 00:07:34,246 --> 00:07:38,362 time means you can focus your efforts on other aspects of the problem. 124 00:07:38,362 --> 00:07:41,985 As beginners, though, we're going to steer clear of all this, and 125 00:07:41,985 --> 00:07:45,182 focus our efforts on algorithms with polynomial runtimes. 126 00:07:45,182 --> 00:07:49,433 Since we're much more likely to work with, and learn about such algorithms. 127 00:07:49,433 --> 00:07:52,086 Now that we know some of the common complexities, 128 00:07:52,086 --> 00:07:56,712 in the next video, let's talk about how we determine the complexity of an algorithm. 129 00:07:56,712 --> 00:07:58,697 Because there are some nuances.