Space Complexity & Review

[00:00:00]
>> Bianca Gandolfo: Space complexity, I'm gonna pass the mic to you guys. So given our conversation about time complexity, what do you think space complexity is all about?
>> Speaker 2: [INAUDIBLE] How much memory?
>> Speaker 3: Dealing with stacks and queues, possibly? I'm not super familiar, but.
>> Bianca Gandolfo: Yeah, yeah, so space is good, yeah.

[00:00:27]
So stacks and queues, those are data structures. And it's all about the space that it takes up in memory, right? So if your algorithm is copying your array a bunch of times, right? And you're making a new array, then in memory you're having five arrays, and that's a certain amount of space complexity.

[00:00:45]
And it works on the same scale of constant, linear, etc., as time complexity. Except that instead of the number of operations that are being executed, we're thinking about how much more space are we taking up. So are we for every loop creating a new array? Okay, so that's like n times the length of the array of space every time.

[00:01:08]
Or if we're what we call sorting in place, where we don't make a new array, and then our space complexity is constant even though our algorithm's time complexity could be something totally different. So things to think about when you're thinking about space complexity is are you making a new data structure?

[00:01:27]
How often are you doing it in comparison to your input? And also with your call stack. If you're doing recursion, that's another thing to consider is that stack is also taking place in memory. However, that's not something you probably need to go in depth about in an interview.

[00:01:50]
Just be aware to just mention that when you're talking about space complexity with recursion. And we're gonna go through a lot of recursion, so we'll see that in action. All right,
>> Bianca Gandolfo: So here's some words, lots of words. Something that you should know from this slide is that there are other notations.

[00:02:11]
We just typically use big O notation which is the worst case scenario. But there's also like the average case scenario and the best case scenario and all these different ones. And you can learn about it by following that link. However, in interviews it's expected that we speak in the pessimistic big O notation.

[00:02:27]
What is the worst case scenario of this algorithm?
>> Bianca Gandolfo: So this is just a review, worst case scenario we're gonna drop any non-significant operation or constants.
>> Bianca Gandolfo: Break.