1
00:00:00,878 --> 00:00:01,379
Next up,
2
00:00:01,379 --> 00:00:05,597
let's look at the situation we encountered
with the linear search algorithm.
3
00:00:05,597 --> 00:00:09,768
We saw that in the worst case scenario,
whatever the value of n,
4
00:00:09,768 --> 00:00:13,259
John took exactly that many
tries to find the answer.
5
00:00:13,259 --> 00:00:16,842
As in linear search,
when the number of operations to
6
00:00:16,842 --> 00:00:21,617
determine the result in the worst case
scenario is at most the same as n,
7
00:00:21,617 --> 00:00:24,741
we say that the algorithm
runs in linear time.
8
00:00:24,741 --> 00:00:27,604
We represent this as O(n).
9
00:00:27,604 --> 00:00:32,203
Now, you can read that as big O of n, like
I just said, or you can say linear time,
10
00:00:32,203 --> 00:00:33,499
which is more common.
11
00:00:33,499 --> 00:00:38,291
When we put that up on a graph against
constant time and logarithmic time,
12
00:00:38,291 --> 00:00:40,546
we get a line that looks like this.
13
00:00:40,546 --> 00:00:45,425
Any algorithm that sequentially reads
the input will have linear time.
14
00:00:45,425 --> 00:00:50,726
So remember any time you know a problem
involves reading every item in a list,
15
00:00:50,726 --> 00:00:52,778
that means a linear runtime.
16
00:00:52,778 --> 00:00:57,143
As you saw from the game we played,
Britney's strategy using binary search was
17
00:00:57,143 --> 00:00:59,892
clearly better, and
we can see that on the graph.
18
00:00:59,892 --> 00:01:05,120
So if we had the option, why would we use
linear search, which runs in linear time?
19
00:01:05,120 --> 00:01:08,289
Remember, that binary
search had a precondition,
20
00:01:08,289 --> 00:01:10,312
the inputs that had to be sorted.
21
00:01:10,312 --> 00:01:13,655
While we won't be looking at
sorting algorithms in this course,
22
00:01:13,655 --> 00:01:18,155
as you learn more about algorithms, you'll
find that sorting algorithms have varying
23
00:01:18,155 --> 00:01:20,863
complexities themselves,
just like search does.
24
00:01:20,863 --> 00:01:25,568
So we have to do additional work
prior to using binary search.
25
00:01:25,568 --> 00:01:30,368
For this reason in practice linear
search ends on being more peformant on
26
00:01:30,368 --> 00:01:34,930
the certain value on n, Because
the combination of sorting first and
27
00:01:34,930 --> 00:01:37,939
then searching using
binary search adds up.
28
00:01:37,939 --> 00:01:42,295
The next common complexity you will
hear about is when an algorithm runs in
29
00:01:42,295 --> 00:01:43,357
Quadratic Time.
30
00:01:43,357 --> 00:01:45,957
And the word Quadratic
sounds familiar to you,
31
00:01:45,957 --> 00:01:49,017
it's because you might have
heard about in Math class.
32
00:01:49,017 --> 00:01:54,395
Quadratic is a word that means
an operation raised to the second power or
33
00:01:54,395 --> 00:01:56,557
when something is squared.
34
00:01:56,557 --> 00:02:00,556
Let's say you and your friends
are playing a tower defense game and
35
00:02:00,556 --> 00:02:03,996
to start it off you're going
to draw a map of the terrain.
36
00:02:03,996 --> 00:02:05,833
This map is going to be a grid and
37
00:02:05,833 --> 00:02:09,529
you pick a random number to to
determine how long this grid is.
38
00:02:09,529 --> 00:02:11,991
Let's set n the size of the grid to 4.
39
00:02:11,991 --> 00:02:15,478
[SOUND] Next, you need to come up
with a list of coordinates, so
40
00:02:15,478 --> 00:02:18,578
you can place towers and
enemies and stuff on this map.
41
00:02:18,578 --> 00:02:20,296
So, how do we do this?
42
00:02:20,296 --> 00:02:24,971
If we start out horizontally,
we'd have coordinate points that go (1,1),
43
00:02:24,971 --> 00:02:27,493
(1,2), (1,3) and (1,4).
44
00:02:27,493 --> 00:02:32,076
Then you go up one level, vertically,
and we have points (2,1), (2,2),
45
00:02:32,076 --> 00:02:33,681
(2,3) and (2,4).
46
00:02:33,681 --> 00:02:38,926
Go up one more and you have the points
(3,1), (3,2), (3,3) and (3,4).
47
00:02:38,926 --> 00:02:44,991
And on that last row, you have the points
(4,1), (4,2), (4,3) and (4,4).
48
00:02:44,991 --> 00:02:46,954
Notice that we have a pattern here.
49
00:02:46,954 --> 00:02:49,480
For each row,
[SOUND] we take the value and
50
00:02:49,480 --> 00:02:53,062
then create a point by adding
to that every column value.
51
00:02:53,062 --> 00:02:56,544
The range of values go
from 1 to the value of n.
52
00:02:56,544 --> 00:02:58,865
So we can generally think of it this way.
53
00:02:58,865 --> 00:03:04,256
For the range of values from 1 to n,
for each value in that range, we create
54
00:03:04,256 --> 00:03:09,582
a point by combining that value with
the range of values from 1 to n again.
55
00:03:09,582 --> 00:03:11,265
Doing it this way for
56
00:03:11,265 --> 00:03:16,512
each value in the range of 1 to n
recreate an n number of values,
57
00:03:16,512 --> 00:03:22,254
and we end up with 16 points,
which is also n times n, or n squared.
58
00:03:22,254 --> 00:03:26,220
This is an algorithm with
a quadratic run time, because for
59
00:03:26,220 --> 00:03:30,677
any given value of n, we carry out
n squared number of operations.
60
00:03:30,677 --> 00:03:34,566
Now, I picked a relatively easy,
so to speak, example, here,
61
00:03:34,566 --> 00:03:39,405
because in English, at least, we often
denote map sizes by height times width.
62
00:03:39,405 --> 00:03:44,391
So we would call this a four by four grid,
which is just another way of saying,
63
00:03:44,391 --> 00:03:46,171
four squared or n squared.
64
00:03:46,171 --> 00:03:50,267
In O notation,
we would write this as big O(n2), or
65
00:03:50,267 --> 00:03:54,463
say that this is an algorithm
with a quadratic runtime.
66
00:03:54,463 --> 00:03:58,075
Many search algorithms have
a worst case quadratic runtime,
67
00:03:58,075 --> 00:04:00,027
which you'll learn about soon.
68
00:04:00,027 --> 00:04:02,407
Now, in addition to quadratic runtimes,
69
00:04:02,407 --> 00:04:06,716
you may also run into Cubic Runtimes
as you encounter different algorithms.
70
00:04:06,716 --> 00:04:10,083
In such an algorithm,
for given value of n,
71
00:04:10,083 --> 00:04:14,182
the algorithm executes
n^3 number of operations.
72
00:04:14,182 --> 00:04:17,110
These are as common as
quadratic algorithms though, so
73
00:04:17,110 --> 00:04:20,797
you won't look at any examples,
but I think it's worth mentioning.
74
00:04:20,797 --> 00:04:25,210
Thrown up on our graph [SOUND] quadratic
in cubic run times look like this.
75
00:04:25,210 --> 00:04:29,878
So this is starting to look pretty
expensive computationally as they say.
76
00:04:29,878 --> 00:04:34,382
We can see here that for small changes
in n is a pretty significant change in
77
00:04:34,382 --> 00:04:37,375
a number of operations
that we need to carry out.