Question

the solution of the recurrence relation t(m) = t( 3m 4) + 1 is

Answer 1

We can solve this using substitution method.

Claim: T(n) <= c n^2

IH: We assume that claim is true for all values of n < m.  

Inductive Step: T(m) = T(m/4) + T(3m/4) + m^2

<= cm^2/16 + c 9 m^2 / 16 + m^2

= cm^2 (1/16 + 9/16 + 1/c)

= c m^2 (10/16 + 1/c)

<= c m^2   as long as 1/c <= 6/16.   So, we can choose a value of c >= 16/6 and the rest of the math holds up.

QED.

Therefore, by PMI, T(n) <= c n^2, that is, T(n) = O(n^2).

Alternative Proof:

Follow the same logic, but instead of c, use a larger constant such as 10.

T(n) = 10 n^2/16 +  10 9n^2/16 + n^2.

      <= 10 n^2