Transcript from the "Initial Time Complexity for a BST" Lesson

[00:00:00]

>> Bianca Gandolfo: Any big takeaways from this, anything new that you learned?

>> Speaker 2: No, the whole thing was kind of new to me, the whole traverse thing. And when you first put up the picture of the first traversal or whatever, I did not at all get how it was gonna work.

[00:00:15] So the whole thing was new to me.

>> Bianca Gandolfo: Cool, so what took you from, I had no idea how it was going to work, to okay maybe I have some inkling?

>> Speaker 2: It was when you were talking about it and I guess just walking through it the first time.

[00:00:36]

>> Bianca Gandolfo: Cool, so like the pseudocode-

>> Speaker 2: Yeah

>> Bianca Gandolfo: Component. Cool, anyone else have that same reaction? You're like, god I have no idea, how to even approach this. No everyone's like, that's it this is gonna be easy.

>> Speaker 3: I think one takeaway is the trees are really made for recursion, right.

[00:00:56]

>> Bianca Gandolfo: Yeah, exactly, so when we think of recursive data structures, we think of trees, for sure.

>> Speaker 4: How they're super nice, and neat. And I guess it also makes sense that you have three different ways you can traverse it cuz you have at any point in time a little triangle.

[00:01:10]

>> Bianca Gandolfo: There's more than three ways, but yeah.

>> Speaker 4: But yeah.

>> Bianca Gandolfo: Yeah, we'll get there.

>> Bianca Gandolfo: So many ways.

>> Speaker 3: I know that the recursion make easy life, and how to catch up the tree that is left right self, I get.

>> Bianca Gandolfo: Yeah, so you are saying that recreation makes your life easier and then the concept of the self left right.

[00:01:47]

>> Speaker 3: Yeah.

>> Bianca Gandolfo: Helps you kind of see the patern?

>> Speaker 3: Right.

>> Bianca Gandolfo: And then it applies like, literally to the code. And, I don't know, I don't feel like recursion always clicks for me like that. With a pattern, your're like, that pattern makes sense to me 100% where I can really spell it out.

[00:02:04] So, I really like that about it too, cool. So what have we done so far with our tree?

>> Bianca Gandolfo: So here's our binary search tree.

>> Bianca Gandolfo: What have we done? What's the first thing we did today?

>> Speaker 2: Insert?

>> Bianca Gandolfo: Yup, so we built it, we learned how to insert things into our binary search tree, in the correct order, right?

[00:02:32] That's the whole point of a binary search tree is there's an order there. What else did we do?

>> Speaker 5: We learned how to check for a value.

>> Bianca Gandolfo: Yeah, so we did contains, so we searched for specific values.

>> Bianca Gandolfo: What else?

>> Bianca Gandolfo: Nothing else?

>> Speaker 2: We learned different ways to traverse.

[00:02:59]

>> Bianca Gandolfo: Yeah, so we also traversed, totally. So we built it, we peeked around. Let's think about, for a moment time complexity for the operations that we've done so far. So we talked about insert.

>> Bianca Gandolfo: What do you think is,

>> Bianca Gandolfo: Sort of the average case insertion if you had just average in your minds based on this picture?

[00:03:28]

>> Bianca Gandolfo: Quick and dirty average.

>> Speaker 3: Login?

>> Bianca Gandolfo: Log in, why do we think it's login?

>> Speaker 3: That's the height.

>> Bianca Gandolfo: Yeah, login is gonna be the height of the tree. And it's also because we're gonna be splitting our problem in half every single time. So anything where we split the problem in half.

[00:03:48] Just like we did the phone book example, that's a binary search, where we split it in half and throw the half of it away.

>> Bianca Gandolfo: So when we have a tree like this and we are splitting the problem in half, we can expect it to be login.

>> Bianca Gandolfo: I see some furrowed brows.

[00:04:12]

>> Speaker 4: Is that for contains or for searching?

>> Bianca Gandolfo: For insertion.

>> Speaker 4: Insertion.

>> Bianca Gandolfo: What about for contains slash a search, right? So search is contains, it's the same thing.

>> Bianca Gandolfo: So let's say the we needed to search for 18.

>> Bianca Gandolfo: First of all how many nodes do we have, we can count?

[00:04:38] So we have 4, 8, 12, 14, we have 15 nodes here. How many steps would it take for us to find 18?

>> Bianca Gandolfo: So we start here, so one, two, well, one, two, three, and then four.

>> Bianca Gandolfo: So probably like four steps.

>> Bianca Gandolfo: Yeah, and then if we doubled that.

[00:05:16]

>> Bianca Gandolfo: How would that change?

>> Bianca Gandolfo: Or what if we just cut it in half?

>> Speaker 4: You went to 15?

>> Bianca Gandolfo: And we just had this, yeah, we just had this one.

>> Bianca Gandolfo: So then, we only have three one, two, three. What if we cut it in half again?

[00:05:41] Then it's just two steps, right one, two. So as the problem grows, the operations grow by how much?

>> Bianca Gandolfo: Half, right? Does that make sense? So when we have 15 or so, it's gonna take us 4 times to get to 18, when we cut it in half, right?

[00:06:13] So we throw away this left side, it's gonna take us three. And we throw away the other half, it'll just take us two.

>> Bianca Gandolfo: And that's logarithmic, there's two.

>> Bianca Gandolfo: Yeah?

>> Speaker 4: How do you know two that again?

>> Bianca Gandolfo: Login, so O of login.

>> Speaker 4: Okay.

>> Bianca Gandolfo: Yeah.

[00:06:41]

>> Bianca Gandolfo: So O parentheses login. Not O of N login which is different. What would make this N login?

>> Bianca Gandolfo: Like what makes an operation N login versus login?

>> [INAUDIBLE]

>> Bianca Gandolfo: Yeah, every time you cut it in half, you have to also do a linear operation.

>> Speaker 5: Right.

[00:07:03]

>> Bianca Gandolfo: Yeah, so multiply it times n, yeah. To like merge sort or quick sort where we have to iterate through the entire thing. So if you were traversing a tree and transforming it?

>> Bianca Gandolfo: So what is a tree traversal then?

>> Bianca Gandolfo: So just visiting every node? So say this tree is 15.

[00:07:40] How many operations do we have to take to visit every node?

>> Speaker 2: 15, right.

>> Bianca Gandolfo: 15, what about if there's 30?

>> Speaker 2: It's always gonna be linear, right?

>> Bianca Gandolfo: Linear, exactly, yeah.

>> Bianca Gandolfo: Yeah, so something that could make it more than linear is if whatever function that you're calling inside of this tree.

[00:08:08] Does something also that is linear, so if your callback function has maybe a loop in it that loops through n times, the same n, right? So n meaning the number of nodes, that would make it what?

>> Speaker 5: N login. n times n.

>> Bianca Gandolfo: Times n, okay. Which is quadratic, yep.