Consider the algorithm below, which identifies the elements of an array that are no larger than a given threshold.

A) Prove that hi lo n 2i + 1 after iteration i of the outer repeat loop of SmallElements, for every iteration. I.e., hi lo n 1 after the first iteration, n 3 after the second, and so forth.

Hint: you may wish to use lo_old to represent the value of lo at the end of the previous iteration and lo_new to represent the value of lo at the end of the current iteration, and similar variables for hi.

B) Use the previous claim to prove that the outer loop terminates.

Input: data: an array of integers Input: n: the length of data Input: t: threshold value Output all elements of data that are S t 1 Algorithm Small Elements 2 lo 0 3 hi n 1 4 repeat repeat lo lo 1 7 until data lo t or his lo repeat hi hi 1 10 until data hil Stor his lo 11 if hi lo then return data 1. lo 1] 12 13 end 14 Swap data lo and data hi 15 until 1