1 votes 1 votes 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)+n2 d) a) T(n)=4T(n)+n Algorithms algorithms recurrence-relation + – अनुराग पाण्डेय asked Sep 7, 2015 अनुराग पाण्डेय 6.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes $$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)$ Digvijay Pandey answered Sep 7, 2015 Digvijay Pandey comment Share Follow See 1 comment See all 1 1 comment reply अनुराग पाण्डेय commented Sep 7, 2015 reply Follow Share Thank you laser. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes $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)$ habedo007 answered Nov 20, 2020 habedo007 comment Share Follow See all 0 reply Please log in or register to add a comment.