Question 3: Consider the following recurrence: T(n)=n+T(n/5)+T(7n/10). In class, we have seen that T(n)=O(n). In this question, you will prove this using the recursion tree method. Recall from class: The root represents the recursion tree on an input of size n. Consider a node u in the recursion tree that represents a recursive call on an input of size m. Then we write the value m at this node u, we give u a left subtree which is a recursion tree for an input of size m/5, and we give u a right subtree which is a recursion tree for an input of size 7m/10. In this way, T(n) is the sum of the values stored at all nodes in the entire recursion tree. Below, we assume that the levels in the recursion tree are numbered 0,1,2,, , where the root is at level 0 . For each i0, let Si be the sum of the values of all nodes at level i. - Determine S0. - Determine S1. - Determine S2. - Use induction to prove the following claim: For every i0, Si(9/10)in. Hint: Consider level i, let k=2i, and let the values stored at the nodes at level i be m1,m2,,mk. What are the values stored at the nodes at level i+1 ? - Complete the proof by showing that T(n)=O(n)