13.3 Checkpoint: An Exercise
Some much needed practice.
Last updated
Some much needed practice.
Last updated
Exercise: Apply techniques 2A and 2B to dup2
.
Calculate the counts of each operation for the following code with respect to N.
Predict the rough magnitudes of each one.
Note: It's okay if you were slightly off—as mentioned earlier, you want rough estimates.
Let us compare the dup1
table with the dup2
table:
dup1
table:
dup2
table:
We can see that dup2
performs significantly better than dup1
in the worst case!
One way to rationalize this is that it takes fewer operations for dup2
to accomplish the same goal as dup1
.
Operation | Symbolic Count | Count (for N=10000) |
---|---|---|
Operation | Symbolic Count | Count (for N=10000) |
---|---|---|
Operation | Symbolic Count | Count (for N=10000) |
---|---|---|
A better realization is that the algorithm for dup2
scales much better in the worst case (e.g. ( vs )
An even better realization is that parabolas () always grow faster than lines ().
i = 0
1
1
j = i+1
0 to
0 to 10,000
<
0 to
0 to 9,999
==
1 to
1 to 9,999
array accesses
2 to
2 to 19998
i = 0
1
1
j = i+1
1 to
1 (in the best case) to 10000 (in the worst case)
<
2 to
2 to 50,015,001
+= 1
0 to
0 to 50,005,000
==
1 to
1 to 49,995,000
array accesses
2 to
2 to 99,990,000
i = 0
1
1
j = i+1
0 to
0 to 10,000
<
0 to
0 to 9,999
==
1 to
1 to 9,999
array accesses
2 to
2 to 19998