Please answer question 7, thanks for your help!

+ 6. (16 points) Guess a plausible solution for the complexity of the recursive algorithm charac- terized by the recurrence relations T(n) =T(n/2)+T(n/4)+T(n/8)+T(n/8)+n; T(1) = 0 using the Substitution Method. (1) Draw the recursion tree to three levels (levels 0, 1 and 2) showing (a) all recursive executions at each level, (b) the input size to each recursive execu- tion, (c) work done by each recursive execution other than recursive calls, and (d) the total work done at each level. (2) Pictorially show the shape of the overall tree. (3) Estimate the depth of the tree at its shallowest part. (4) Estimate the depth of the tree at its deepest part. (5) Based on these estimates, come up with a reasonable guess as to the Big-Oh complexity order of this recursive algorithm. Your answer must explicitly show every numbered part described above in order to get credit. 7. (10 points) Use the Substitution Method to prove that your guess for the previous problem is indeed correct. Statement of what you have to prove: Base Case proof: Inductive Hypotheses: Inductive Step