Please use induction for the proof

3. Consider the following algorithm to answer the following question. Let n 2 0 be the number of people in line. This algorithm takes as input a list ai,.. . , an of heights, in centimeters, of the people in line, starting with the height a1 of the first person in the line. We assume for simplicity that all the heights are distinct, so there are no two people of the exact same height. The algorithm returns the number of people who can see to the front of the line, in other words, the number of people in the line who are taller than everybody before them in the line. More formally, this is fi: for all j ajl For example, on input 154,170, 166,175,161, 185, the algorithm would return 4, as there are four people who are taller than everyone before them, shown in bold NumCanSeeRec(a1,. .. , an : list of n 2 1 distinct heights) (a) if n-1 then (b)return 1 (c) c= umCanSeeRee(a1, (d) for i :-1 to n -1 (e) if ai > an then ,an-1) return c (g) return c+1 Answer the following questions about this algorithm. Please show your work (a) (3 points) For a fixed n, a best-case input to this algorithm is an input list of size n where the number of comparisons (of heights) is as small as possible (only count the comparison on line (e)) How many comparisons does the algorithm do on a best-case input of size n? Give a closed-form (non-recursive) formula in terms of n (b) (3 points) For a fixed n, a worst-case input to this algorithm is an input list of size n where the number of comparisons (of heights) is as large as possible (only count the comparison on line (e)) Write down a recurrence for the exact number of comparisons done by this algorithm on an input of size n, in the worst case (c) (3 points) Describe the runnne in notation of this algorithm on a worst case input (d) (6 points) Prove the correctness of this algorithm 3. Consider the following algorithm to answer the following question. Let n 2 0 be the number of people in line. This algorithm takes as input a list ai,.. . , an of heights, in centimeters, of the people in line, starting with the height a1 of the first person in the line. We assume for simplicity that all the heights are distinct, so there are no two people of the exact same height. The algorithm returns the number of people who can see to the front of the line, in other words, the number of people in the line who are taller than everybody before them in the line. More formally, this is fi: for all j ajl For example, on input 154,170, 166,175,161, 185, the algorithm would return 4, as there are four people who are taller than everyone before them, shown in bold NumCanSeeRec(a1,. .. , an : list of n 2 1 distinct heights) (a) if n-1 then (b)return 1 (c) c= umCanSeeRee(a1, (d) for i :-1 to n -1 (e) if ai > an then ,an-1) return c (g) return c+1 Answer the following questions about this algorithm. Please show your work (a) (3 points) For a fixed n, a best-case input to this algorithm is an input list of size n where the number of comparisons (of heights) is as small as possible (only count the comparison on line (e)) How many comparisons does the algorithm do on a best-case input of size n? Give a closed-form (non-recursive) formula in terms of n (b) (3 points) For a fixed n, a worst-case input to this algorithm is an input list of size n where the number of comparisons (of heights) is as large as possible (only count the comparison on line (e)) Write down a recurrence for the exact number of comparisons done by this algorithm on an input of size n, in the worst case (c) (3 points) Describe the runnne in notation of this algorithm on a worst case input (d) (6 points) Prove the correctness of this algorithm