Assume that a deterministic recursive algorithm A initially takes an input with size N, which is an even integer. For each recursive call, A scans entire input for each element of the input with a constant additional overhead K after the scan, and divides the input into equal pieces, and calls itself on these inputs (call them as left and right parts). The base-case of recursive call occurs once the size of input reaches to one. a. Write the recurrence expression T(N) for algorithm A [5pt].
b. Explain the execution time complexity of A via T(N), write the complexity in Big- Oh notation.