Problem Solving

$1.$

$$ Write the pseudocode for the Insertion Sort algorithm and analyze its time complexity.

$$ Given an array of integers, write a Divide$-$and$-$Conquer algorithm to find the maximum subarray sum. Explain the time complexity of your solution.

$2.$ Solve the following recurrence relation using the recursion tree method: T$($n$)=2$T$($n$/2)+$ n$.$ Assume T$(1)=1.$

Explain the properties of Red$-$Black Trees and provide a pseudocode for insertion. Discuss how these properties ensure the tree remains balanced.