You are given an n by n matrix of distinct integers such that all rows and all columns are increasing. that is, every row read left to right is an increasing sequence of integers and every column read from top to bottom is an increasing sequence of integers. you would like to determine if a given integer k is in the matrix. you can access any entry of the matrix, and it costs one unit of time to compare two different entries of the matrix or to compare an entry with any number of your choice.

come up with a "divide and conquer" algorithm that solves this problem by splitting the matrix into quadrants. explain why your algorithm is correct.

write a recurrence for the running time of this algorithm.

determine the big-o time complexity of this algorithm. for full credit your algorithm should beat the obvious θ(n2) time complexity. for bonus credit, give an o(n) time algorithm