Problem $2.$ Divide and Conquer

$1.$ Complete the multiple choice questions on Gradescope $($the assignment called "Homework $7($recurrences$)")$

$2.$ Suppose there is a line of $\backslash ($ n $\backslash )$ cells. The neighbors of a cell are the cells directly to the left and right $($if they exist$).$

Each cell $\backslash ($ i $\backslash )$ contains a value $\backslash ($ A$[$i$]\backslash ),$ and no two cells have the same value. We say a cell is a peak if it has a larger value than both of its neighbors $($or its one neighbor, if it is at one of the two ends$).$

Your goal is to find an algorithm that takes as input an array $\backslash ($ A $\backslash )$ of values and returns the location of a peak. For example, on input $\backslash ($ A$=[5,4,3,6,2,7,0,-1,-2]\backslash ),$ your algorithm could return $0,3$ or $5($indexing from $0),$ since all those locations are peaks.

Note that at least one peak must exist in the array, since no two cells have the same value.

$($a$)$ You first consider a greedy approach: starting at a random cell, you check if it is a peak. If it is$,$ you are done, If not, move to the neighboring cell with the higher value and repeat. Show that this greedy approach reads $\backslash (\backslash$Omega$($n$)\backslash )$ cells in the worst case $($that is$,$ give a type of input where it must read a large part of the array$).$

$($b$)$ Write an algorithm that solves this problem and reads $($at most$)\backslash ($ O$(\backslash$log n$)\backslash )$ cell values in the worst case.