\ T(n)=3\ T(n/2)+2\ log_{10}n;\ T(1)=1;\ n=2^k & \\ where k=log_{2}n & \\ We know that log_{10}n=log_{2}n/log_{2}10=k/log_{2}10 & \\ T(1) = T(2^0) = 1 & \\ T(2) = T(2^1) = 3\ T(2^0)+1*2/log_{2}10=3+1*2/log_{2}10 & \\ T(4) = T(2^2) = 3\ T(2^1)+2*2/log_{2}10=3*(3+1*2/log_{2}10)+2*2/log_{2}10 \ \ \ \ \ \ \ = 3^2+(3+2)*2/log_{2}10 & \\ T(8) = T(2^3) = 3\ T(2^2)+3*2/log_{2}10=3*(3^2+(3+2)*2/log_{2}10)+3*2/log_{2}10 \ \ \ \ \ \ \ = 3^3+(3^2+3*2)+3)*2/log_{2}10 & \\ T(16) = T(2^4) = 3\ T(2^3)+4*2/log_{2}10 \ \ \ \ \ \ \ =3*(3^3+(3^2+3*2)+3)*2/log_{2}10)+4*2/log_{2}10 \ \ \ \ \ \ \ = 3^4+(3^3+3^2*2+3*3+4)*2/log_{2}10 & \\ From the above relations, we guess & \\ T(2^k)= 3^k+(3^{k-1}+3^{k-2}*2+3^{k-3}*3+.....+3*(k-1)+k)*2/log_{2}10 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =3^k+((3^{k-1}+3^{k-2}+.....+1)+(3^{k-2}+3^{k-3}+.....+1)+(3^{k-3}+3^{k-4}+.....+1)+(3^{k-4}+3^{k-5}+.....+1)+.....+1)*2/log_{2}10 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =3^k+((3^k-1)+(3^{k-1}-1)+(3^{k-2}-1)+(3^{k-3}-1)+.....+(3-1))/log_{2}10 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =3^k+((3/2)*(3^k-1)-k)/log_{2}10 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =3^k+(3^{k+1}-4k+3))/2log_{2}10 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(1+3/2log_{2}10)3^k-(k+3/2)/log_{2}10 & \\ So, T(n)= (1+3/2log_{2}10)3^{log_{2}n}-(log_{2}n+3/2)/log_{2}10 & \\ Since this is a guess, we check by induction. & \\ We get T(n/2) = (1+3/2log_{2}10)3^{log_{2}n-1}-(log_{2}n-1/2)/log_{2}10 & \\ Now we know that T(n)=3 T(n/2)+2*log_{2}n/log_{2}10 \ \ \ \ \ = 3*((1+3/2log_{2}10)3^{log_{2}n-1}-(log_{2}n-1/2)/log_{2}10)+2*log_{2}n/log_{2}10 \ \ \ = (1+3/2log_{2}10)3^{log_{2}n}-(3*(log_{2}n-1/2)+2 log_{2}n)/log_{2}10 \ \ \ = (1+3/2log_{2}10)3^{log_{2}n}-(log_{2}n+3/2)/log_{2}10, hence\ verified.