So what might an algorithm be for a problem that we might want to solve?
Well, consider this.
This is an old school problem where you might
have lots and lots of names and lots of lots of numbers,
and those names are hopefully sorted alphabetically from A through Z
in a book like this.
And even though most of us don't really reach for this technology anymore,
consider that it's really the same as your iPhone or Android phone
or other device, which has all of your contacts top to bottom
and you can scroll through them from A to Z,
or you can search for them by typing into the little autocomplete box.
How is even your phone solving this problem?
Well let's consider a simple approach.
I'm going to look at the first page and look for someone on the phone book.
Suppose that person's name is Mike Smith, last name starting
with S. Let me go ahead and look down.
He's not here.
Let me turn the page.
This is an algorithm.
It's a step-by-step process for solving a problem, finding Mike Smith.
Is this algorithm correct, would you say?
Yeah.
I mean, it's pretty slow, it's pretty stupid, in that it's going to take,
my God, forever, like, hundreds of page turns to find Mike Smith.
But if he's there, I will find him according
to this step-by-step approach.
What if I speed things up a bit just because it's tedious, otherwise?
So I do two, four, six, eight, 10, 12, 14, 16 and so forth.
Is that algorithm faster?
Absolutely.
Literally twice as fast.
Is it correct?
AUDIENCE: No.
DAVID MALAN: No.
Why?
[INTERPOSING VOICES]
DAVID MALAN: Yeah, we might skip them.
I might get unlucky and eventually, I might get to the S's.
But darn it if Mike wasn't in between two pages as I turn them at once.
So it's not a fatal flaw.
That algorithm, I could fix by just saying
if you hit the T section or maybe Sn instead of Sm, just back
up one or so pages just to fix that bug or mistake, so to speak.
But it, at least, is twice as fast.
But if this phone book has 1,000 something pages,
it's still going to take me maybe 500 pairwise turns just to find Mike Smith.
That's a while just to look someone up.
But most of us, if you've used this technology,
instead, did what, back in the day?
Go roughly to the middle if there aren't little letters on the side off
which to cheat.
So roughly into the middle.
I'm in the M section.
Now the M's, of course, mean that Mike is not this way,
which would be the A's.
He's probably this way toward the Z's because S, of course,
is between the M and the Z.
So at this point, I can literally tear the problem in half,
throw half of the problem away very dramatically and unnecessarily,
making the point that we've now gone from 1,000 some odd pages to what?
500.
And I can do it again.
Ah, I went a little too far.
I'm now in the T section, so I can tear the problem in half again,
throw that half away, and now I'm down from 1,000 to 500 to 250 pages
only, after just two steps in this step-by-step process.
And if I repeat this again and again and again, hopefully, I'll
be left, ultimately, with, say, just one page on which
Mike Smith either is or is not.
And I can call him or quit.