Video 1-12: Jumplists search analysis

0:03 Uh, with that we can set up a recursion for analyzing the search costs in these jump lists. And again, remember the search strategy is just you start here. Let's say we search for um, key 15.

0:20 I would start here and check whether I can use the shortcut jump pointer. That goes to 18, it's too far, so I cannot. So, instead I have to walk one step. Now, I know that there's a key one here, but it's less likely that I I'm searching for this one because it's the minimum of the entire sublist. So, I'm not even going to look at the one. I'd rather take the shortcut and compare with the three. Now, 15 is bigger, so I can definitely do that jump and continue from the three. And likewise here for the three, I find a shortcut to 12. I can take that, so I do. And similar here, now with another jump I'm at the 15 and then I'm done. Uh, if I had searched for 14 instead, here I I would have not been able to take this. Then this last bit I have to walk along the linked list.

1:13 But usually there's only one or two steps, right? Yep. Yeah, you figure out who goes first. Is it greedy search or am I just not getting it? Yeah, it's greedy, but uh, that's good enough because this is sorted, right? This I'm thinking of breadth-first search now. Yeah, way simpler. It's It's a sorted list, so in each step you know whether you should follow the jump pointer or not. It's no, uh, yeah. You could say it's breadth-first search. Okay. Right? Yeah. And you only check the identity of the node when you need to walk. Yeah, so I I check the pointers that the jump pointers go to. There I check the key because I need to know whether I can take the shortcut. Uh, and the first time I I'm told I cannot take the shortcut. And if that element doesn't have a jump pointer anymore, so I I take the edge to the next element.

2:15 Uh, and then I might have to remember where I came from. The last time I declined to take the shortcut. I could have searched for for I have an example here. Uh, say we search for nine. So, the the beginning is the same. Can't take 18. But I can take the three. I can't take 12, so I go down here. I can't take six, so I can go here, but I cannot take 11. So, I need to go back. I cannot take 10, so I need to go back. At this point I have to start comparing with the seven and the eight and the nine. Because which one of these it is, uh, this is unclear.

3:08 I think what is the insertion order of these elements? Uh, I have not not told you yet anything about the insertions. Um, uh, so far it's this hypothetical world where I'm giving you all the keys in advance and then I'm building a random structure on top. This is unrealistic, right? We never have this this situation. Uh, we'll have to talk about how to do the insertions in a bit. Um, first I wanted to, uh, briefly analyze how long the search path is. And you could phrase it in this picture as if you do a a breadth-first search from this header, how long are the typical paths until you reach an element? That's precisely it. So, breadth-first search in this directed graph. And then automatically you would always take the shortcuts because they're shorter, right?

4:02 Uh, you can you can specify this recursively. So, here, um, D is supposed to be the expected depth of any of these elements, so depth in the breadth-first search tree. If I have only a single node, then I don't have any key, so there's nothing and then zero is base case. If I have a single key, then, um, this is the case of two nodes. Uh, I'm doing uh, gaps. Sorry, not not, uh, stored keys. So, with a single node, the header has minus infinity as a key, so there's only one option where where I could have gone to. And that's after the minus infinity.

5:03 For two nodes, uh, stay. I could have taken this or this gap. So, by gap I mean I'm searching for a key that's not there. I'm searching for something between two keys or bigger than all keys, smaller than all keys. Again, here this is minus infinity in both cases. This is some actual key. So, here I have two choices. In the first case, I do not follow any pointers. Um, I'm just, uh, finding right there that I uh, I have this. I would have to compare with X. I guess cost for comparisons would be one. But here it's the number of pointers that we followed. And for this element I would follow the one uh, next pointer. That's how the numbers here come about. Uh, for larger lists, there's the two options. Uh, well, three if you're strict. I have the minus infinity. Then there's one gap that I can only reach from the header.

6:03 And I have to check this in a way now. With probability one over M, one over the possible gaps, I'm searching for this this element smaller than everything in this jump list. Then I have to do this from the header. In all other cases, there's some elements with gaps and there's some jump pointer from the header.

6:30 And now it depends, uh, which gap I'm looking for, whether I follow the jump pointer or stay in the next list. So, uh, this probability is about where the jump pointer goes to.

6:52 So, the sum iterates over all the indices J that I can point to with my jump pointer and that's the probability of doing so. And then here this J over M, that's the J gaps in this part.

7:10 And here I have M minus one minus J gaps. If I'm searching for one of the J gaps in this part, I'm not taking the jump pointer, but I take this one next pointer. So, I have one extra pointer I followed plus whatever whatever happens in the next sublist. Similarly, if I do follow the jump pointer because I'm looking for one of these gaps, I have one jump pointer that I followed plus whatever happens in the jump sublist. That's a lovely recurrence and you can try to solve it. Um, the first step towards that is to multiply by M, so I'm not taking the expected depth, but rather I pretend I'm summing over all. So, I'm searching every gap once. You can divide by M again at the end. It just makes some of the formulas a bit nicer because then you can cancel this uh, these fractions away. So, multiplying by M really just cancels these guys.

8:10 Uh, they occur on on all the sides, so that helps to make things a little less ugly. Uh, verbally mentioned. Um, I'll define a a variable that abbreviates this M times DM. Same otherwise, then the recursion you can simplify a little bit. Uh, these two sums are completely symmetric. Here I'm summing J DJ. Here I'm summing M minus one minus J, D M minus one minus J. If you check the ranges, this starts with J at one and goes up to M minus two. This starts, if I put the largest J in, at one and goes to J minus M minus two or J equals one. So, they both go over the same range. And this also makes sense. The next list and the jump sub next sublist and the jump sublist, they do the same thing. They're uniformly chosen, so they behave the same for the search costs as well.

9:16 And so you get this recurrence with the two here and the same sum. Now again, uh, here's what the quick sort recurrence looks like for the average case. If you've seen this before, maybe you rec- recognize it.

9:34 Some people spend way too much time, uh, solving these kind of recurrences. Um, here you can do a simple trick to get an upper bound at least. You can note that element-wise for each M, this cost that we are interested in is less than the respective costs in in this recurrence. And because this one can be be exactly, you can upper bound our result with the solution for that, and that's where you get this from. But again, I think it's it's sufficient in our case um to cite this as a result, and if you want to know more, you'll uh you'll have to dig through solving these recurrences.