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.