n301/Complexity n301.tplt Figure2.10

Algorithm to find the largest value in a list Figure2.10

Figure2.11

First draft of the pattern-matching algorithm Desigman "Genes" Genes: Sequence of nucleotides Human genome: over 100,000 genes => 3.5 billion nucle. A genes ~= over 10,000 nucleotides A probe: search pattern for a gene ex: Genome: ...TCAGGCTAATCG...
Probe: TAATC A pattern matching problem. Matching process

step 1: T1 T2 T3 T4 T5 ... -> source
P1 P2 P3 ... -> target
Step 2: T1 T2 T3 T4 T5 ...
-------->P1 P2 P3
slide

Analysis of Algorithms Sequential Search for n items

unit of work = compares

Best case: 1 (first item) Worst case: n (last or missing item) Average case: n/2 Housekeeping (advancing index)

a constant multiple

Figure 3.6

Work = 2n Figure 3.7

Work = cn for various values of c Figure 3.8

Growth of Work = cn,br>for Various values of c Order of magnitude Sequential search is linear:0(n)

shape of graph
constant does not affect shape

Processing 2-D table is quadratic

o(n²)
shape of graph

0(n²) always gets bigger than 0(n) eventually Figure 3.10

Work = cn²for carious values of c Figure 3.11

A comparison of n and n² Comparison Pentium Pro 200 runs at bout 75 megaflops (75 million floating-point operations per second Cray T3E-900 can achieve speeds of 670 gigaflops (670 billion floating-point operations per second Race between Tortoise and Hare Pentuim runs the 0(n) algorithm and the Cray runs the 0(n²) algorithm Comparison 2 timing result:

n	Pc	Cray
750	0.00001 sec	0.00000084 sec
7,500	0.0001 sec	0.000084 sec
75,000	0.001 sec	0.0084 sec
750,000	0.01 sec	0.84 sec
7,500,000	0.1 sec	84 sec
75,000,000	1 sec	8400 sec = 2.3 hr
750,000,000	10sec	840,000 sec = 9.7 days

Comparison 3 At beginning the Cray has the lead, but by the end the Pentium surpassed the Cray "The order of magnitude of the algorithm being executed can play a more important role than the raw speed of the computer. Figure 3.13

A Comparison of two extreme 0(n²) and 0(n) algorithms Selection Sort Input: unsorted list Output: sorted list Algorithm

find max value in unsorted section
swap with last value in unsorted section

Selection Sort Algorithm 1. Get values for n and the n list items 2. Set the marker for the unsorted section at the end of the list 3. Repeat step 4 through 6 until the unsorted section of the list is empty

4. Select the largest number in the unsorted section of the list
5. Exchange this number with the last number in the unsorted list
6. Move the marker for the unsorted section forwards one position

7. Stop Sort Example

     output               input
    2 3 5 7 8  <---   5 7 2 8 3

Unsorted List Sorted List
5 7 2 8 3
5 7 2 8 3
5 7 2 3 8
5 2 3 7 8
2 3 5 7 8
2 3 5 7 8
2 3 5 7 8
Explanation of example To put 8 in place in the list 5, 7, 2, 8, 3 | Compare 5 (largest so far) to 7

Unsorted List	Sorted List
5 7 2 8 3
5 7 2 8 3
5 7 2 3	8
5 2 3	7 8
2 3	5 7 8
2	3 5 7 8
	2 3 5 7 8

7 becomes largest so far

Compare 7 (largest so far) to 2 Compare 7 (largest so far) to 8

8 becomes largest so far

Compare 8 to 3 Total number of comparisons: 4 (which is 5 - 1) Explanation of example 2 To put 7 in place in the list 5, 7, 2, 3 | 8 Compare 5 (largest so far) to 7

7 becomes largest so far

Compare 7 to 2 Compare 7 to 3 7 is the largest Total number of comparisons: 3 (Which is 5 - 2) Explanation of example 3 To put 5 in place in the list 5, 3, 2 | 7, 8 Compare 5 (largest so far) to 3 Compare 5 to 2 5 is the largest Total number of comparison: 2 (which is 5 - 3) Explanation of example 4 To put 3 in place in the list 2, 3 | 5, 7, 8 Compare 2(largest so far) to 3 3 is the largest Total number of comparisons: 1 (which is 5 - 4) Selection Sort Analysis Work unit = comparisons

done in finding maximum element

(n -1) + (n - 2) + ... + 1

(1/2)n² - (1/2)n + swapping
0(n²)

Binary Search algorithm Requires sorted list Work unit = compares Compare at successive minpoints as list gets cut in half Work = number of times n is divisible by 2 = log₂(n) = lg n lg n = 0(lg n)

shape of curve

Binary Search Algorithm (list must be sorted) 1. Get values for NAME, n, N₁, ..., N_n and T₁, ..., T_n 2. Set the value of beginning to 1 and set the value of Found to NO 3. Set the value of end to n 4. Repeat steps 5 through 10 until either Found = YES or end is less than beginning Binary Search Algorithm (list must be sorted) 2

5. Set the value of m to the middle value between beginning and end.
6. If NAME is equal t N_m, then name found at the midpoint between beginning and end, then do step 7 and 8

7. Print the telephone number of that person, T_m
8. Set the value of Found to YES

Binary Search Algorithm (list must be sorted) 3

9. Else if NAME precedes N_m alphabetically, then set end = m - 1
10. Else (NAME foloows N_m alphabetically) set beginning = m + 1

11. If (Found = NO) then print the message 'I am sorry but that name is not in the directory' 12. Stop Figure 3.20

Binary Search Tree for a Seven-Element List Figure 3.21

Values for n and lg n Figure 3.22

A Comparison of n and lg n Figure 3.23

Order-of-Magnitude Time Efficiency Summary Orders of magnitude 0(n²) = walking 0(n) = driving 0(lg n) = flying Brute force algorithm Hamiltonian circuit problem Trace all paths in a graph

work unit = examine path
suppose only 2 choices per node
2ⁿ paths, exponential

0(2ⁿ) Too costly, too slow, impractical Figure 3.24

Four Connected Cities Figure 3.25

Hamiltonian Circuits among all paths from A in figure 3.24 with four links Explanation For n-node city, the bottom of the tree has 2ⁿ nodes ans 2ⁿ path to examine 0(2ⁿ) ==> exponential Figure 3.26(a)

Comparisons of lg n, n², and 2ⁿ Figure 3.27

A comparison of four orders of magnitude Orders of Magnitude - 2 0(lg n) = flying 0(n) = driving 0(n²) = walking 0(n³) = crawling 0(n⁴) = barely moving 0(n⁵) = no visible progress 0(2ⁿ) = forget it, it will never happen