00:00:00,080 --> 00:00:02,955 DAVID MALAN: --we'll generally call a loop, some kind of cycle, because it's making me do something again. DOUG LLOYD: So as we discussed a little bit earlier, we're making a conscious effort here to introduce students to concepts without introducing them too much to the heavy theoretical math that might be behind these. And so this demonstration about falling onto the phone book example where we did the counting by one page, counting by two pages, then showing binary search, gives us a way to show the different powers or speeds of these algorithms without getting too heavy into the math just yet. DAVID MALAN: Yeah, and I think it's a nice way too of throwing away the distractions of what might be this plot with an x-axis and a y-axis, and really just allowing students to intuitively grasp that, OK, size of problem gets bigger that way and time to solve gets bigger that way, and I think that's pretty intuitive. And we certainly don't need to slap a formal analysis at this point in the semester, we'll come back to this in a few weeks' time. But I think it's reasonable at this point to introduce N as just a generic term for the number of pages, show the distinction between N and N over 2. And what I try to do generally, especially if I'm doing this demo not on a digital screen but on like a chalkboard, is draw a vertical line as I'm sort of imaginatively doing with my finger here to point out that every line on the yellow line is half as high as the red line. But this is what's really important, and indeed this is deliberate, the sort of stop light approach of red is bad, yellow is OK, green is great. DOUG LLOYD: Yeah, it's a simple reinforcement, but it does really hammer home that point. DAVID MALAN: And what's powerful too here, if you have enough of a classroom to walk left and right on here, especially if you can exceed the screen, to point out that that green line really, it does grow, and it doesn't flatten out, but it grows so slowly that you can be way over there and have a huge number of pages, but the time to solve is still pretty low. DOUG LLOYD: Right, with 4 billion pages in the phone book, the first example you've got 4 billion, with the yellow line there it's 2 billion, but with the green line it's only 32 steps to do it. DAVID MALAN: And that's what's pretty powerful. And that's why I think it's important in class to actually fast forward to pretty big numbers, the 4 billion which at least has the relevance of being 2 to the 32, but to point out to students just, my god, you go from that many pages so quickly to just one, it's I think more compelling than to only go up to 1,000 pages where dividing it in 10 times is great but it's not as magical. DOUG LLOYD: It doesn't have that impact. I agree.