Example of SELECT (k, S) algorithm S = < 1, 10, 8, 5, 6, 3, 5, 4, 2, 4, 7, 5, 8, 8, 9, 24, 6, 16, 20, 11, 4, 3, 14, 19, 2 > Divide into subsequences of 5 and sort each: 1 2 5 6 2 5 3 7 11 3 6 4 8 16 4 M, the sequence of medians 8 4 8 10 10 5 9 220 14 24 19 Find the median m of M, and rearrange the columns: 2 2 1 5 6 3 3 5 7 11 4 4 6 8 16 m, the median of M 4 14 8 8 5 19 10 9 220 20 24 S1 = < 1, 5, 3, 5, 4, 2, 4, 5, 4, 3, 2> S2 = < 6,6> S3 = <10, 8, 7, 8, 8, 9, 24, 16, 20, 11, 14, 19 > SELECT (5, S) SELECT (5, S1) SELECT (12, S) SELECT (13, S) SELECT (17, S) SELECT (20, S) answer is 6 answer is 6 SELECT (4, S3) SELECT (7, S3) etc. |S1|= 11 | S2 | = 2 |s3| = 12 2 2 IA IɅ N≤3 ≤ + 4 IA 3 N≤M≤ < 4 IɅ VI ΙΛ 15516) IɅ 5 7 8 00 6 11 16 elements known to be less than or equal to m 4 14 8 8 20 VI 5 19 10 9 24 16 elements known to be greater than or equal to m 20 2 2 1 5 6 3 3 5 7 11 4 4 6 VI 8 VI IA ΙΛ 4 14 8 8 ΙΛ IɅ 5 19 10 9 6≤2≤2 24 Those elements in the green box are known to be less than or equal to m, the number of such elements is at least (3/5) x (1/2) x n = (3/10)n. Contrapositively, the number of elements greater than m is at most n - (3/10) n = (7/10) n. Therefore, the recursive call at Line 12, SELECT (k - |S1| - |S2, S3) takes time at most T(7n/10). Similarly, the elements in the blue box are guaranteed to be greater than or equal to m, and the number of such elements is at least (3/10)n. So the number of elements less than m is at most (7/10)n, and the recursive call at Line 10, SELECT (k, S1) also takes time at most T(7n/10). Note that depend on the choice for the length of the subsequences (in the algorithm discussed in class and the example above, the subsequences are of length 5) and n (number of elements in S), the two boxes may not be of equal size, in which case the recursive calls at Line 12 and Line 10 (observe that only one of the two may be executed) will have different complexities, and the larger one will dominate the expression for T(n).