algorithms

2. (10 points) Solving Recurrences (II). Consider the following recurrence: T(n)=2T(n/4)+T(n/8)+n Assume that the base case is T(1)=(1). Using the recurrence tree method: (a) (8 points) Find an upper bound (i.e. O(.))onthesolutiontothisrecurrence. (b) (2 points) State the lower bound (i.e. (.))forT(n) and justify your