Practice the Substitution method, recursive tree method, and master theorem on the following:i) F(n)=n∗F(n−1)ii) T(n) = 1, when n=1=1+T(n-1) when n>1iii) Fn=Fn−1+Fn−2.iv) T(n)=4T(n/2)+n^2v) T(n)=2T(n/2)+n

i) F(n)=nF(n−1) This is a recursive function where each function call multiplies the result of the previous function call by n. To solve this using the substitution method, we would start by substitifying F(n-1) with (n-1)F(n-2), and so on, until we reach the base case. The result would be F(n) = n(n-1)(n-2)*...21 = n!.

ii) T(n) = 1, when n=1 =1+T(n-1) when n>1 This is a simple recursive function where each function call adds 1 to the result of the previous function call. The result would be T(n) = n, because each function call adds 1, and there are n function calls.

iii) Fn=Fn−1+Fn−2. This is the Fibonacci sequence, where each number is the sum of the two preceding ones. To solve this using the recursive tree method, we would start by drawing a tree with Fn as the root, and Fn-1 and Fn-2 as the children. We would then continue drawing the tree for each child, until we reach the base case. The result would be the sum of all the nodes in the tree.

iv) T(n)=4T(n/2)+n^2 This is a divide and conquer algorithm, where each function call divides the problem size by 2 and adds n^2. To solve this using the master theorem, we would compare it to the standard form aT(n/b) + f(n). Here, a=4, b=2, and f(n)=n^2. Since a > b^d (where d is the degree of f(n)), we are in case 1 of the master theorem, and the time complexity is O(n^log_b(a)) = O(n^2).

v) T(n)=2T(n/2)+n This is another divide and conquer algorithm, where each function call divides the problem size by 2 and adds n. To solve this using the master theorem, we would compare it to the standard form aT(n/b) + f(n). Here, a=2, b=2, and f(n)=n. Since a = b^d (where d is the degree of f(n)), we are in case 2 of the master theorem, and the time complexity is O(n^dlog(n)) = O(nlog(n)).