Question

Here is a recursive algorithm that answers the same question as posed on Group HW3, finding the number of people who are taller than everyone before them in line. NumCanSeeRec(a1,... , an : list of n 2 1 distinct heights) (a) ifn -1 then (b return 1 (c) c= ŅumCanSeeRee(a1, , an-1) d) for i:- 1 ton- 1 (e) if a, an then 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 runtime in Θ notation of this algorithm on a worst case input (d) (6 points) Prove the correctness of this algorithm

Answer 1

Pls give thumbs up

a) The best case will be the people are standing in the ascending order of their heights i.e. the first person a1 is the smallest, a2 is the second smallest and so on

a1 < a2 < a3 < ... < an

In this case, the line will not even trigger a single time

(b)

The worst case will be the people are standing in the descending order of their heights i.e. the first person a1 is the tallest, a2 is second tallest and so on

a1 > a2 > a3 > ... > an

In this case, the line will trigger every time

(c) The run time of this will be Theta(n), since there is a single loop getting excercised from 1 to n

(d) The algorithm is correct since we are counting the comparison of the people with the last standing person and incrementing the count, if we see a match of this comparison