recurrence realtion

Question

$T(n) = \begin{Bmatrix} T(\frac{n}{k})+T(\frac{3n}{4})+n\ \ \ if\ n\geq2\\ 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if\ n=1 \end{Bmatrix}$

Comments

The question doesn't tell anything about what is 'K'

Is it n/4 by any chance

I mean there is somekind of typing mistake

Answer 1

yeah it shld be n/4;

then the solution is by tree method

at each level work done is n

and the height of tree is  log n to the base 4/3;

therefore total work done is n*log n to the base 4/3