Amortized Analysis
Projects
7.19 |
Complete Figure 7-22. |
7.20 |
Complete Figure 7-23. Drop any fractions and approximate very large values using scientific notation as shown. You will probably have to use both a calculator/computer and some algebra to accomplish this. |
ArrayList |
LinkedList |
|||||||
---|---|---|---|---|---|---|---|---|
Best |
Avg |
Amort |
Worst |
Best |
Avg |
Amort |
Worst |
|
add() |
Q(1) |
Q(n) |
||||||
contains() |
Q(1) |
Q(n) |
Q(n) |
|||||
get() |
Q(1) |
Q(n) |
||||||
isEmpty() |
||||||||
iterator() |
||||||||
remove() |
||||||||
size() |
Q(n) |
Q(n) |
Q(n) |
Q(n) |
Time to process n elements (milliseconds) |
1 second |
1 minute |
1 hour |
1 day |
1 year |
---|---|---|---|---|---|
log2 n |
1018,061 |
||||
n |
1,000 |
60,000 |
3.1 x 1010 |
||
n log2 n |
|||||
n2 |
1,897 |
||||
n3 |
|||||
2n |
9 |