Binary Search Time Complexity

[00:00:00]
>> Bianca Gandolfo: So that was our binary search tree. Let's compare a little bit the time complexity here. So, for the search, the binary search is going to be O ( h ) where h is the height of the tree. The height of this tree is 1, 2, 3, 4.

[00:00:35]
>> Bianca Gandolfo: So that's something to note for a binary search on the array. So this is a binary search on a tree. Binary search on an array is going to be O(log n). Linear search of an array is going to be O(n). So given that our binary search tree can be really unbalanced.

[00:01:00]
An unbalanced tree is when the differences of the height of a subtree is larger than one, okay? So, this subtree has a height of 1, 2, 3. This sub tree has a height of 1 and 2. The difference in the heights is 1. So this is considered a balanced tree.

[00:01:28]
But before we saw that really long one, right, it depends on the insert order how your binary search tree is shaped, right? So it can be really really long and in the worse case, you can always insert them in order. So, it'd be like one, two, three, and it would just be like really long link list essentially.

[00:01:50]
And then your time complexity of H is going to be the length.
>> Bianca Gandolfo: Of the number of values that you're inserting. So it's going to be the same as a linear search. That make sense? So there are dangers with using the binary search tree if it's unbalanced. And that's something that we should keep on top of our mind.

[00:02:16]
We use binary search trees, and it's like this topic of interview questions quite often, but it's just something you know that, if it's not balance, it's actually not that useful to us. What else did I want to tel you about this?
>> Speaker 2: Can you repeat that again? So how did you determine if it was unbalanced?

[00:02:39]
>> Bianca Gandolfo: If the height of the subtrees are different. So we have our root node and then we have this left subtree, and then we have this right subtree. So this one has a height of 1,2, 2 subtree, this tree has a height of 1,2,3. That's the height. So two minus three is one.

[00:03:05]
So it's balanced. But if we added like one more here, then it would be unbalanced because the difference would be 2.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yeah, so basically, when you insert it, you don't want to insert too much on one side and not enough on the other side, yeah.

[00:03:26]
So some strategies for balancing is adding rules about how you can insert. Like more rules other than the left or the right has to be greater than or less than. And the other things is, as you're inserting and deleting, reshuffling and rotating your binary search tree,
>> Speaker 2: The make contains a duplicate so it's kind of a-

[00:03:44]
>> Bianca Gandolfo: Yeah, that's a typo. This was supposed to be five up there. Anyway, we could talk about insert really quick. So for the binary search on an array, it's just an array. So the insert and delete for both of those are going to be linear. And for the binary search tree, the insert and delete is also going to be proportional to the height.

[00:04:13]
>> Speaker 2: The total height? Like so it would be three in this particular case.
>> Bianca Gandolfo: The high here is one, two, three, four.
>> Speaker 2: It's four, okay.
>> Bianca Gandolfo: Yeah, and what else do I want to tell you about this? So you might be wondering like what's the point of a binary search tree at this level, and it's actually not that fast.

[00:04:37]
Like we use it all the time in this interview settings, but like why is it even exist? It's useful for searching when you need to have order. So it can be faster when it's balanced, then in array, a sorted array. And you can insert and delete much easier if it's balanced.

[00:05:02]
However, when it's unbalanced, you might as well just use an array pretty much. And we should note that if order doesn't matter, right, so like our linear search, order doesn't really matter. We can always use a hash table. Everybody, don't forget. We have a hash table. If you need to look something up really fast, hash tables always going to do it for you in constant time.

[00:05:29]
So we only really want to use these binary search trees, one, when they're balanced, and two, when order is really important for your problem. So if order doesn't matter, or you can even optimize, just optimize everything with a hash table, which is a JavaScript object in our world.

[00:05:47]
So that's my pro tip, is don't forget, don't over complicate it by doing the binary search tree or binary search. First think, if I'm searching for something, can I just throw it in a hash table? You might be able to, even in things that seem kind of weird.

[00:06:09]
It's worth considering, and it's also much easier.