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.