Many search problems can be expressed as follows: given a search space S, determine if some target t is in S.we are given a sorted array with n elements and the goal is to determine if a key k is stored in the array. The typical approach is to perform some kind of "action" so that once the outcome of the action is obtained, weve either found the target or weve shrunk the search space S by a significant amount. Repeat this action over and over again and weve found the target or weve shrunk the size of S down to 1 (or some constant).n the later case, checking the remaining element(s) in S will solve the problem. In binary search, the action is to compare the middle element m in the array with k. Based on the answer, weve either found k or shrunk the search space by half. There are many ways of shrinking the size of S. Given the conditions below, determine how many times S should be shrunk.

i. (1 pt.) Assume S has n elements. An action removes r elements from S. We want to shrink S so that it has at most 10 elements left.

ii. Assume S has n^ 2 elements. An action removes r^2 elements from S. We want to shrink S so that it has at most 10 elements left.

iii. Assume S has n elements. An action decreases the size of S by 70%.

iii. We want to shrink S so that it has at most 1 element left. iv. Assume S has n^2 elements. An action decreases the size of S by 1%. We want to shrink S so that it has at most 1 element left.

iv. Your answers to the first two questions should be in terms of n and r while those for the last two questions should be in terms of n only. Assuming r is a constant, order the functions from the slowest-growing to the fastest growing. Indicate if any two of them have the same growth rate (i.e. if they are of each other)