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.

Figure 7-22. Comparison of algorithms from our ArrayList and LinkedList classes, for Project 7.19. (Analyze the version of remove() which takes an index as an argument.)

 

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)

Figure 7-23. Number of elements that can be processed in a given amount of time for various running-time functions. For Project 7.20.

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

       

Категории