Asymptotically compare 14 T(n/4) + O(n) and 7 R(n/2) + O(n).

Question

Asymptotically compare recurrence relations T and R.  Express your answer by writing asymptotic relation between T and R.

T(n) = 14 T(n/4) + O(n).              R(n) = 7 R(n/2) + O(n).

Answer 1

Using masters theorem: a=14 b=4
n^log_4(14) = n^1.9 > n
T(n) = O(n^log_4(14))

Using masters theorem: a=7 b=2
n^log_2(7) = n^2.8 > n
R(n) = O(n^log_2(7))

T(n) = o(R(n) as n^1.9 < n^2.8