1. BIG-OH SUM (i = 1 to n-3) { SUM(j = 1 to (i+4)/2) {3} + 1 } + SUM(i = 1 to 100) {1} SUM (i = 1 to n-3) { 3(i+4)/2 + 1 } + 100 SUM (i = 1 to n-3) { 3(i+4)/2 } + SUM (i = 1 to n-3) {1} + 100 3/2 SUM (i = 1 to n-3) { i+4 } + (n-3) + 100 3/2 (SUM (i = 1 to n-3) {i} + 3/2 SUM (i = 1 to n-3) {4}) + (n-3) + 100 3/2 ((n-3)(n-2)/2) + 6(n-3) + (n-3) + 100 3/4 (n^2 - 5n + 6) + 6n - 18 + n - 3 + 100 (3/4)n^2 - (15/4)n + (9/2) + 6n - 18 + n - 3 + 100 (3/4)n^2 + (13/4)n + (167/2) = O(n^2) 2. SORTING [ 7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9] a. bubble x 3 1 [ 1, 6, 7, -3, 8, 4, 12, 2, 21, -1, 9, 30] 2 [ 1, 6, -3, 7, 4, 8, 2, 12, -1, 9, 21, 30] 3 [ 1, -3, 6, 4, 7, 2, 8, -1, 9, 12, 21, 30] b. selection x 4 1 [-3, 1, 6, 12, 7, 8, 4, 21, 2, 30, -1, 9] 2 [-3, -1, 6, 12, 7, 8, 4, 21, 2, 30, 1, 9] 3 [-3, -1, 1, 12, 7, 8, 4, 21, 2, 30, 6, 9] 4 [-3, -1, 1, 2, 7, 8, 4, 21, 12, 30, 6, 9] c. insertion x 5 1 [ 1, 7, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9] ^ 2 [ 1, 6, 7, 12, -3, 8, 4, 21, 2, 30, -1, 9] ^ 3 [ 1, 6, 7, 12, -3, 8, 4, 21, 2, 30, -1, 9] ^ 4 [-3, 1, 6, 7, 12, 8, 4, 21, 2, 30, -1, 9] ^ 5 [-3, 1, 6, 7, 8, 12, 4, 21, 2, 30, -1, 9] ^ d. merge (recursive calls) [-3, 1, 6, 7, 8, 12, -1, 2, 4, 9, 21, 30] | e. quick (partition) [ 9, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 7] pivot to end i j [-1, 1, 6, 12, -3, 8, 4, 21, 2, 30, 9, 7] i j [-1, 1, 6, 2, -3, 8, 4, 21, 12, 30, 9, 7] i j [-1, 1, 6, 2, -3, 4, 8, 21, 12, 30, 9, 7] j i [-1, 1, 6, 2, -3, 4, 7, 21, 12, 30, 9, 8] 3. TREES AND HEAPS a. BST: i. after adds: m / \ d x / \ / \ b i s z / \ / \ g k r t \ \ h w ii. after removing k: m / \ d x / \ / \ b i s z / / \ g r t \ \ h w iii. after removing t: m / \ d x / \ / \ b i s z / / \ g r w \ h iv. after removing x: m / \ d z / \ / b i s / / \ g r w \ h v. after removing m: r / \ d z / \ / b i s / \ g w \ h b. AVL: m \ x \ z imbalance at m (case 4): Left rotate x / \ m z / \ d s / b imbalance at x (case 1): Right rotate m / \ d x / \ / \ b i s z / / \ g r t \ w imbalance at x (case 2): Left-Right rotate m / \ d t / \ / \ b i s x / \ / / \ g k r w z \ h imbalance at d (case 3): Right-Left rotate m / \ g t / \ / \ d i s x / / \ / / \ b h k r w z c. Min binary heap i. after adds: m / \ x z / s bubble up s m / \ s z / \ x d bubble up d d / \ m z / \ / x s b bubble up b b / \ m d / \ / \ x s z i / t bubble up t b / \ m d / \ / \ t s z i / \ x r bubble up r b / \ m d / \ / \ r s z i /\ / x t g bubble up g b / \ g d / \ / \ r m z i /\ /\ / x t s w k bubble up k b / \ g d / \ / \ r m k i /\ /\ /\ x t s w z h bubble up k b / \ g d / \ / \ r m h i /\ /\ /\ x t s w z k ii. removes #1 returns b; bubbles down k d / \ g h / \ / \ r m k i /\ /\ / x t s w z #2 returns d; bubbles down z g / \ m h / \ / \ r s k i /\ /\ x t z w #3 returns g; bubbles down w h / \ m i / \ / \ r s k w /\ / x t z 4. SET PROGRAMMING Part A: protected void intersect(StringTreeNode node, StringSet other, StringSet intersection) { if (other == null) { return; } if (node != null) { intersect(node.left, other, intersection); if (other.contains(node.data)) { intersection.add(node.data); } intersect(node.right, other, intersection); } } Part B: The in-order traversal of s1 is going to hit each node in s1 so it is O(N). Then since s2 is a StringTreeSets (i.e. BSTs), s2 could be a completely degenerate tree (basically linked lists). If this were the case, for each node examined in s1, other.contains could take O(N) at least half of the time as it is a completely degenerate tree and may have to traverse all of its elements to find out it does not contain node.data. Lastly, intersection.add will be executed 1/2 the time and it could takes worst case O(N) time if the StringTreeSet, intersection, we are creating is completely degenerate as well. So we have O(N) * O(N) * O(N) = O(N ^3).