CS6515 HW1

Graded Problem
Please see Ed Discussion for details on the form and content ofa Divide & Conguer algorithm
You are given an n x n matrix M with distinct entries. Two entries, M[i]lj] and M[s][t], areneighbors if they are adjacent. That is |i-s|+|j-t|=1 (refer to the visualization below).An entry is a local maximum if it is strictly larger than all its neighbors. Design a divide andconguer algorithm with an O(n log n) runtime to find a local maximum, returning it’sposition (i, j) in matrix M.
Describe your algorithm in words (no pseudocode!) and justify its correctness. Analyzeand justify the algorithm’s runtime in Big-O notation.
Your answer must be typed and submitted as a PDF to Canvas (no embedded pictures orimages).
Neighboring entries of the grey (middle) entry are the entries marked in red. Note that entries inthe boundary have three or two neighbors only.