1. Find the worst-case time complexity for the OddMedian algorithm below. Show all work.

You may use the facts that you can add an element to an array in ?(1), remove an element from an array in ?(1), find the size of an array in ?(1), and find the minimum or maximum of an array of size x in ?(x) time. You may assume that lo and hi both have O(i) elements during every iteration of the for loop.

2. Find the worst-case time complexity for the StrangeSum algorithm below. Show all work.

3. Develop a recurrence for the worst-case time complexity for the abSearch algorithm below. Show all work. When describing the recurrence, you may assume that n is even; that is, that ?n/2? = ?n/2? = n/2.

Input: str: a string of length n Input: n: the length of str Output: the first index i such that str-a and strlib, or -1 if str doesn't oontain the subsing "ab" Algorithm: abSearch 2 if n