1
00:00:00,335 --> 00:00:01,916
At the beginning of this series,
2
00:00:01,916 --> 00:00:05,820
I mentioned that there were two ways of
measuring the efficiency of an algorithm.
3
00:00:05,820 --> 00:00:08,149
The first was time complexity, or
4
00:00:08,149 --> 00:00:11,934
how the runtime of an algorithm
grows as N grows larger.
5
00:00:11,934 --> 00:00:14,233
The second is space complexity.
6
00:00:14,233 --> 00:00:17,523
We took a pretty long route
to build up this example, but
7
00:00:17,523 --> 00:00:20,821
now we're in a good place to
discuss space complexity.
8
00:00:20,821 --> 00:00:25,322
Space complexity is a measure
of how much working storage or
9
00:00:25,322 --> 00:00:29,745
extra storage is needed as
a particular algorithm grows.
10
00:00:29,745 --> 00:00:32,557
We don't think about it much these days,
but
11
00:00:32,557 --> 00:00:36,493
every single thing we do on
a computer takes up space in memory.
12
00:00:36,493 --> 00:00:41,268
In the early days of computing,
considering memory usage was of paramount
13
00:00:41,268 --> 00:00:45,303
importance because memory was limited and
really expensive.
14
00:00:45,303 --> 00:00:48,519
These days we're spoiled,
our devices are rich with memory.
15
00:00:48,519 --> 00:00:53,479
This is okay when we write everyday
code because most of us aren't dealing
16
00:00:53,479 --> 00:00:55,810
with enormously large data sets.
17
00:00:55,810 --> 00:01:00,703
When we write algorithms however, we
need to think about this because we want
18
00:01:00,703 --> 00:01:04,617
to design our algorithms to
perform as efficiently as it can,
19
00:01:04,617 --> 00:01:07,953
as the size of the data set,
N, grows really large.
20
00:01:07,953 --> 00:01:09,509
Like time complexity,
21
00:01:09,509 --> 00:01:14,811
space complexity is measured in the
worst-case scenario using big O notation.
22
00:01:14,811 --> 00:01:19,158
Since you are familiar with
the different kinds of complexities,
23
00:01:19,158 --> 00:01:21,494
let's dive right into an example.
24
00:01:21,494 --> 00:01:26,921
In our iterative implementation of binary
search, the first one we wrote that uses
25
00:01:26,921 --> 00:01:31,978
a while loop, let's look at what happens
to our memory usage as N gets large.
26
00:01:31,978 --> 00:01:34,486
Let's bring up that function.
27
00:01:34,486 --> 00:01:38,108
Let's say we start off with
a list of ten elements.
28
00:01:38,108 --> 00:01:43,064
Now inspecting the codes we see that our
solution relies heavily on these two
29
00:01:43,064 --> 00:01:44,851
variables first and last.
30
00:01:44,851 --> 00:01:48,357
First points to the start of the list and
last, to the end.
31
00:01:48,357 --> 00:01:52,636
When we eliminate a set of values,
we don't actually create a sublist.
32
00:01:52,636 --> 00:01:57,344
Instead we just redefine first and
last as you see here,
33
00:01:57,344 --> 00:02:01,062
to point to a different
section of the list.
34
00:02:01,062 --> 00:02:05,200
Since the algorithm only considers
the values between first and
35
00:02:05,200 --> 00:02:09,183
last when determining the midpoint,
by redefining first and
36
00:02:09,183 --> 00:02:14,710
last as the algorithm proceeds we can find
the solution using just the original list.
37
00:02:14,710 --> 00:02:18,851
This means that for
any value of n the space complexity of
38
00:02:18,851 --> 00:02:22,913
the interative version of
binary search is constant.
39
00:02:22,913 --> 00:02:27,512
Or that the iterative version of
binary search takes constant space.
40
00:02:27,512 --> 00:02:31,424
Remember that we would
write this as big O of one.
41
00:02:31,424 --> 00:02:34,378
This might seem confusing,
because as n grows,
42
00:02:34,378 --> 00:02:37,919
we need more storage to account for
that larger list size.
43
00:02:37,919 --> 00:02:39,341
Now this is true, but
44
00:02:39,341 --> 00:02:43,777
that storage is not what space
complexity cares about measuring.
45
00:02:43,777 --> 00:02:48,797
We care about what additional storage
is needed as the algorithm runs and
46
00:02:48,797 --> 00:02:50,618
tries to find a solution.
47
00:02:50,618 --> 00:02:55,844
If we assume something simple, say that
for a given size of a list, represented
48
00:02:55,844 --> 00:03:00,685
by a value N, it takes N amount of
space to store it, whatever that means.
49
00:03:00,685 --> 00:03:05,880
Then for the iterative version of
binary search, regardless of how large
50
00:03:05,880 --> 00:03:10,903
the list is, at the start, middle,
and end of the algorithm process,
51
00:03:10,903 --> 00:03:15,037
the amount of storage required
does not get larger than N.
52
00:03:15,037 --> 00:03:18,763
And this is why we consider
it to run in constant space.
53
00:03:18,763 --> 00:03:23,039
Now, this is an entirely different story
with the recursive version, however.
54
00:03:23,039 --> 00:03:27,330
In the recursive version of binary search
we don't make use of variables to keep
55
00:03:27,330 --> 00:03:30,353
track of which portion of
the list we're working with.
56
00:03:30,353 --> 00:03:35,328
Instead, we create new lists every
time with a subset of values, or
57
00:03:35,328 --> 00:03:39,013
sublists, with every
recursive function call.
58
00:03:39,013 --> 00:03:43,314
Let's assume we have a list of size n and
in the worst case scenario,
59
00:03:43,314 --> 00:03:46,036
the target element is
the last in the list.
60
00:03:46,036 --> 00:03:50,596
Calling the Recursive Implementation
of binary search on this list and
61
00:03:50,596 --> 00:03:53,334
target would lead to a scenario like this.
62
00:03:53,334 --> 00:03:55,587
The function would call itself and
63
00:03:55,587 --> 00:03:59,946
create a new list that goes from
the midpoint to the end of the list.
64
00:03:59,946 --> 00:04:05,090
Since we're discarding half the values,
the size of the sublist is N by 2.
65
00:04:05,090 --> 00:04:07,533
This function will keep calling itself,
66
00:04:07,533 --> 00:04:11,300
creating a new sublist that's
half the size of the current one,
67
00:04:11,300 --> 00:04:15,446
until it arrives at a single element list,
and a stopping condition.
68
00:04:15,446 --> 00:04:19,829
This pattern that you see here,
where the size of the sublist is reduced
69
00:04:19,829 --> 00:04:23,263
by a factor on each execution
of the algorithmic logic,
70
00:04:23,263 --> 00:04:25,691
well we've seen that pattern before.
71
00:04:25,691 --> 00:04:26,956
Do you remember where?
72
00:04:26,956 --> 00:04:29,290
This is exactly how binary search works.
73
00:04:29,290 --> 00:04:33,702
[SOUND] It discards half the values
every time until it finds a solution.
74
00:04:33,702 --> 00:04:36,049
Now we know that because of this pattern,
75
00:04:36,049 --> 00:04:38,943
the running time of binary
search is logarithmic.
76
00:04:38,943 --> 00:04:39,543
In fact,
77
00:04:39,543 --> 00:04:44,422
this space complexity of the recursive
version of binary search is the same.
78
00:04:44,422 --> 00:04:49,490
If we start out with the memory allocation
of size N that matches the list,
79
00:04:49,490 --> 00:04:53,007
on each function call of
recursive binary search,
80
00:04:53,007 --> 00:04:57,667
we need to allocate additional
memory of size N/2, N/4, and so
81
00:04:57,667 --> 00:05:02,789
on until we have a sublist that is
either empty or contains a single value.
82
00:05:02,789 --> 00:05:07,447
Because of this, we say that
the recursive version of the binary
83
00:05:07,447 --> 00:05:12,035
search algorithm runs in logarithmic
time with a big O of log N.
84
00:05:12,035 --> 00:05:14,252
Now, there's an important caveat here.
85
00:05:14,252 --> 00:05:16,992
This totally depends on the language.
86
00:05:16,992 --> 00:05:21,233
Remember how I said that a programming
language like Swift can do some tricks to
87
00:05:21,233 --> 00:05:23,493
where recursion depth doesn't matter?
88
00:05:23,493 --> 00:05:25,897
The same concept applies here.
89
00:05:25,897 --> 00:05:30,457
If you care to read more about this
concept, it's called tail optimization.
90
00:05:30,457 --> 00:05:35,218
It's called tail optimization because
if you think of a function as
91
00:05:35,218 --> 00:05:40,226
having a head and a tail, if the recursive
function call is the last line
92
00:05:40,226 --> 00:05:45,486
of code in the function, as it is in
our case, we call this tail recursion,
93
00:05:45,486 --> 00:05:49,774
since it's the last part of
the function that calls itself.
94
00:05:49,774 --> 00:05:53,889
Now the trick that Swift does to
reduce the amount of space, and
95
00:05:53,889 --> 00:05:58,626
therefore computing overhead,
to keep track of this recursive calls,
96
00:05:58,626 --> 00:06:02,762
is called tail call optimization,
or tail call elimination.
97
00:06:02,762 --> 00:06:06,065
It's one of those things that
you'll see thrown around a lot
98
00:06:06,065 --> 00:06:09,703
in algorithm discussions, but
may not always be relevant to you.
99
00:06:09,703 --> 00:06:12,618
Now, what of any this is relevant to us?
100
00:06:12,618 --> 00:06:16,205
Well, Python does not implement
tail call optimization.
101
00:06:16,205 --> 00:06:20,768
So the recursive version of binary
search takes logarithmic space.
102
00:06:20,768 --> 00:06:24,068
If we had to choose between
the two implementations,
103
00:06:24,068 --> 00:06:28,835
given that time complexity or run-time
of both versions, the iterative and
104
00:06:28,835 --> 00:06:33,749
the recursive version are the same,
we should definitely go with the iterative
105
00:06:33,749 --> 00:06:37,599
implementation in Python,
since it runs in constant space.
106
00:06:37,599 --> 00:06:38,946
Okay, that was a lot.
107
00:06:38,946 --> 00:06:43,486
But all of this, with all of this we've
now established two important ways
108
00:06:43,486 --> 00:06:47,308
to distinguish between algorithms
that handle the same task,
109
00:06:47,308 --> 00:06:49,705
and determine which one we should use.