T(n) = T(n/2) + n recurrence equation solution? T(1) = 1.

Question

suppose you are given n bit integers asuming for common sense n as power of 2 .it is required to multiply them using divide and conquer method .what is the divide and conquer recurrence that would arise for the problem

a) T(n)=4T(n/2)+c      

b) a) T(n)=2T(n/2)+n              

c) a) T(n)=4T(n/2)+n²          

d) a) T(n)=4T(n)+n

Answer 1

$$T(n) =  T(n/2) + n$$
Here, $a=1$, $b= 2$, $f(n) = n$, hence the Master Method is applicable.

$n^{\log_2(1)} = n^0 = 1 < f(n)$

So, the answer will be $O(n)$

Comments

Thank you laser.

Answer 2

$T(n)=T(\frac{n}{2})+n$

$\rightarrow T(n)=T(\frac{n}{4})+\frac{3n}{4}$

$\rightarrow T(n)=T(\frac{n}{2^k})+\frac{(2^{k}-1)n}{2^{k-1}} $ – Equation 1

For $T(1)=1, \frac{n}{2^k}=1$

$\rightarrow n=2^k \rightarrow k = logn$

Putting value of $k$ in Equation 1

$T(n)=1+ \frac{(2^{logn} -1)n}{2^{logn -1}}$

Identity: $c^{log_cx}=x$, therefore

$T(n)=1+\frac{(n-1)n}{\frac{n}{2}}\rightarrow T(n)=1+2(n-1)$

Constants are ignored, $T(n)=O(n)$