I need help to solving all the questions

Homework #2 #1 Suppose we know that an algorithm has n classes of complexity for a problem of size n. We have T1(n) = 2, T2(n) = 4, T3(n) = 6 , …, and Tn(n) = 2n. We also know that the probability of each class is the same. Find the average complexity of the algorithm. Homework #2 #2 Suppose we know that an algorithm has 5 classes of complexity for a problem of size n. The complexities T1(n) .. T5(n) are given below. Regarding probabilities, suppose that p1 is twice as likely as p2, p2 is twice as likely as p3, , p3 is twice as likely as p4 and p4 is twice as likely as p5. Ti for all instances: T1(n) = n, T2(n) = 2n, T3(n) =3n4, T4(n) = 4n and T5(n) = 5n (a) Find all five probabilities p1, p2, p3, p4 , p5. [Hint: the sum of all probabilities equal 1.0] (b) Find the A(n) for the algorithm. Homework #2 #3 Suppose we find complexities of two algorithms as follows. Let p be a probability function, i.e. 0.0 ≤ p ≤ 1.0 A1(n) = 4n2p + (n+1)(1-p) A2(n) = n2(1-p) + 8np (a) Determine the range of values for p when A1 executes fewer characteristic operations on average than A2? [Hint, set the inequality, isolate p, and analyze your result] (b) Determine the range of values for p when A1 executes fewer characteristic operations on average than A2 given that n = 100. (c) Determine the range of values for p when A1 executes fewer characteristic operations on average than A2 given that n is a very large number. Homework #2 #4 Find the closed form for the recurrence using the method of characteristic roots. an = 4an-1 – 3an-2 a0 = 2 a1 = 3