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.