15.1 For Loops
Count, count, count...
Now that we've seen some runtime analysis, let's work through some more difficult examples. Our goal is to get some practice with the patterns and methods involved in runtime analysis. This can be a tricky idea to get a handle on, so the more practice the better.
Example One:
Last time, we saw the function dup1, that checks for the first time any entry is duplicated in a list:
We have two ways of approaching our runtime analysis:
Counting number of operations
Geometric visualization
Method 1: Count Number of Operations
Since the main repeating operation is the comparator, we will count the number of "==" operations that must occur.
Method 2: Geometric Visualization
We can also approach this from a geometric view.
Example 2:
Let's look at a more involved example next. Consider the following function, with similar nested for loops:
The outer loop advances by multiplying i
by 2 each time. The inner loop runs from 0 to the current value of i
. The two operations inside the loop are both constant time, so let's approach this by asking "how many times does this print out "hello" for a given value of N?"
Our visualization tool from above helped us see dup1's runtime, so let's use a similar approach here. We'll lay out the grid for the nested for loops, and then track the total number of print statements needed for a given N below.
If N is 1, then i
only reaches 1, and j
is only 0, since 0 < 1. So there is only one print statement:
We can keep filling out our diagram to get a fuller picture. Here it is up to N = 18:
What we see, if we add up all the counts at each stage of the loops, is that the number of print statements is:
(if N is a power of 2).
Again, we can think of this in two ways. Since we're already on a graphical roll, let's start there.
Method 1: Finding the Bound Visually
Method 2: Finding the Bound Mathematically
We can obtain the same result by solving our equation from above with the power of mathematics:
Again if N is a power of 2.
Techniques: No Magic Shortcuts
Unfortunately, they're not. And we know this because we just did two nested for loop examples above, each with different runtimes.
In the end, there is no shortcut to doing runtime analysis. It requires careful thought. But there are a few useful techniques and things to know:
Find exact sum
Write out examples
Draw pictures
We used each of these techniques above.
Also used in the examples above are two important sums you'll see very often:
You saw both of these above, and they'll return again and again in runtime analysis.
Last updated