3. (15 points) Asymptotics. Let n = k2 for some positive integer k. A Sudoku solution is an n xn array of numbers, each in the set {1,..., n}, such that the same number does not occur (1) twice in a row, (2) twice in a column, and (3) twice in a k x k square box, where the whole array is divided into n such boxes. Given an array as input, we want to determine whether it is a Sudoku solution. (a) (5 points) Give an O(n) time algorithm to solve this problem. (b) (5 points) Give an O(na) time algorithm to solve this problem. (c) (5 points) Give an N(n?) lower bound for this problem, by showing that any algorithm that makes fewer than na queries to entries of the input array cannot be correct for all possible inputs. 3. (15 points) Asymptotics. Let n = k2 for some positive integer k. A Sudoku solution is an n xn array of numbers, each in the set {1,..., n}, such that the same number does not occur (1) twice in a row, (2) twice in a column, and (3) twice in a k x k square box, where the whole array is divided into n such boxes. Given an array as input, we want to determine whether it is a Sudoku solution. (a) (5 points) Give an O(n) time algorithm to solve this problem. (b) (5 points) Give an O(na) time algorithm to solve this problem. (c) (5 points) Give an N(n?) lower bound for this problem, by showing that any algorithm that makes fewer than na queries to entries of the input array cannot be correct for all possible inputs