• Quiz Today
• Lab Finals start Tomorrow; Sample on Web

• t = A * N * log(N)

• Various values of N

• N	log(N)	N * log(N)	N^2
  2	1	2	4
  4	2	8	16
  8	3	24	64
  16	4	64	256
  1 K	10	10 K	1 M
  2 K	11	22 K	4 M
  8 K	13	1 M	64 M
  1 M	20	20 M	1 T
  2 M	21	42 M	4 T
  __________	__________	__________	__________

• K = 1024; M = K * K; G = K * M; T = K * G

• Assumes Sorted
• Like Telephone Book
• Logarithmic Time
• t = A * log(N)

• Note: here N is number of moves looking ahead.
• We Have an Algorithm!
• Layers of look ahead: If I do this, then he does this, ....
• Problem Solved (?!)
• Can Represent Possibilities by Tree
• Assume 10 Possibilities Each Move
• t = A * 10^N
• !!!!
• Exponential
• Sample Numbers

• Visit N Cities in Optimal Order
• Optimal By:
  • time
  • distance
  • cost
• N factorial (N!) Possibilities
• Look at Table
• N! is roughly N^N
• Typical of some very practical problems

3	2! = 2		5	4! = 24
abc			abcde
acb 			abced
			abdce
4	3! = 6		abdec
abcd			abecd
abdc			abedc
acbd		
acdb			acbde
adbc			acbed
adcb 			acdbe
			acdeb
			acebd
			acedb
		
			adbce
			adbec
			adcbe
			adceb
			adebc
			adecb

			aebcd
			aebdc
			aecbd
			aecdb
			aedbc
			aedcb

	t = 5.49 * 10**-3 * 2**n
n	t
5	.17s
10	5.62s
15	3.00m
20	1.6h
25	2.13d
30	68.23d
35	5.98y
40	191.3y
45	6120.y
50	196K y
55	6.27M y
60	201M y
65	6.42G y
70	205G y