Proficiency Assignment: A Sort$-$of Sorted Array

Topic: Divide and Conquer.

An array of N entries has an unusual property. Somewhere within is the minimum element. Let's call this index X $.$ The elements to the left of it $($indexes $\backslash (<mi>\backslash </mi>$mathrm$\{$X$\}\backslash ))$ are sorted in descending order, while the elements to the right of it $($indexes $\backslash (>\backslash$mathrm$\{$X$\}\backslash ))$ are sorted in ascending order. First, identify a brute force algorithm to find X and note its runtime. Then, develop a divide and conquer algorithm find $\backslash ($ X $\backslash )$ that is faster than your brute force algorithm. Explain why your algorithm works $($you do not need to formally prove it$),$ show its $\backslash (\backslash$mathrm$\{$T$\}(\backslash$mathrm$\{$N$\})\backslash ),$ and use the Master Theorem to show its runtime.

You will submit a single file containing:

$-$ Your brute force algorithm.

$-$ Your divide and conquer algorithm.

$-$ Your $\backslash (\backslash$mathrm$\{$T$\}(\backslash$mathrm$\{$N$\})\backslash )$ with explanation.

$-$ The runtime according to the Master Theorem.