Solve the following recurrence using the substitution method. Assume a base case of T (1) = 1.1. Find a non-recursive formula for T (N ) in terms of T (1). You will need to establish a pattern for what the recurrence looks like after the k-th iteration. You do not need to formally prove that your patterns are correct via induction, but you will lose points if your patterns are not correct. Your solutions may include integers, n raised to a power, and/or logarithms of n. For example, a solution of the form 8^log(2)n is unacceptable; this should be simplified as n^log(2)8= n3.2. Give the big-O expression for each of the recurrences.i. T (n) = 2 T (n −1) + 1.ii. T (n) = 9 T (n/3) + n2.iii. T (n) = 6 T (n/3) + n.