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.