Chapter 5 "Anlaysis of Algorithms"

Data Structures with Java, Rick Mercer

Answers to Self-Check Questions


Answers to Self-Check Questions, Chapter 5

5-1 order of growth, highest to lowest
	  -1- 2^n  (2 to the nth power)
	  -2- n3
	  -3- 100*n^2
	  -4- 10*n
	  -5- 2*n
	  -6- 1000
	
5-2  n^2 dominates the function
	
5-3 percentage of the function
	  n^2 =  98%
	  10n =  1.96%
	  100 = .0392%
	
5-4 tightest upper bounds
	  -a- O(1)                                -d- O(n)
	  -b- O(n^2) On the order of n squared    -e- O(n)
	  -c- O(n^3)  	                          -f- O(log n)
	
5-5 O(n^2)

5-6 change < to >

5-7 compareT

5-8 run time of reversal = O(n)  (can perform 0.5 * n swaps)

5-9 run time for removal = O(n)  (may have to shift from 1 up to n-1 elements