Chapter 1
I
Introduction to algorithms
14
Algorithm 2
Try this algorithm instead. Fold the paper.
In this example, folding the paper once is an operation.
You just made
two boxes with that operation!
Fold the paper again, and again, and again.
Unfold it after four folds, and you’ll have a beautiful grid! Every fold
doubles the number of boxes. You made 16 boxes with 4 operations!
You can “draw” twice
as many boxes with every fold, so you can draw
16 boxes in 4 steps. What’s the running time for this algorithm? Come
up with running times for both algorithms before moving on.
Answers: Algorithm 1 takes O(
n) time, and algorithm 2 takes
O(log
n) time.
Drawing a grid
in four folds
15
Big O notation
Big O establishes a worst-case run time
Suppose you’re using simple search to look for a person in the phone
book. You know that simple search takes O(
n) time to run, which
means
in the worst case, you’ll have to look through every single entry
in your phone book.
In this case, you’re looking for Adit. This guy is
the first entry in your phone book. So you didn’t have to look at every
entry—you found it on the first try. Did this algorithm take O(
n) time?
Or did it take O(1) time because you found the person on the first try?
Simple search still takes O(
n) time. In this case, you found what you
were looking for instantly. That’s the best-case scenario. But Big O
notation is about the
worst-case scenario. So you can say that, in the
worst case, you’ll have to look at every entry in the phone book once.
That’s O(
n) time. It’s a reassurance—you know
that simple search will
never be slower than O(
n) time.
