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 |