1 votes 1 votes Is this the correct way to solve ? Q) int algorithm(int n) { int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) } Algorithms time-complexity algorithms recurrence-relation + – syncronizing asked Mar 15, 2019 • retagged Mar 19, 2019 by Devshree Dubey syncronizing 1.3k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Shaik Masthan commented Mar 15, 2019 reply Follow Share By the for loops ==> 10.$\frac{n}{2}$ ===> C$_1$.$\frac{n}{2}$. $\text{return 4}*\color{red}{\text{algorithm}(\frac{n}{2})}*\color{green}{\text{algorithm}(\frac{n}{2})}+\color{magenta}{\text{algorithm}(\frac{n}{2})}*\color{blue}{\text{algorithm}(\frac{n}{2})} $ Total four times(red,blue,green,magenta) you are recalling the original problem with the size of half of input. Note that, the return value is different, and the calls are different. Totally ===> T(n) = C$_1$.$\frac{n}{2}$ + 4.T($\frac{n}{2}$) = 4.T($\frac{n}{2}$) + n 3 votes 3 votes ankitgupta.1729 commented Mar 15, 2019 i reshown by Shaik Masthan Mar 15, 2019 reply Follow Share you have written $4T(n/2)*T(n/2)$ for 4*algorithm(n/2)*algorithm(n/2) but 4*algorithm(n/2)*algorithm(n/2) means multiply the return value of algorithm(n/2) by 4 and then again multiply it with return value of algorithm(n/2). * is used for multiplication. if you write 4T(n/2) it means we are calling algorithm(n/2) 4 times , here "4" does not mean we are multiplying by 4 in return value of algorithm(n/2). Here, 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) involves 3 multiplication and 1 addition operation which are of constant cost i.e. O(1) for each function call and here overall we are calling algorithm(n/2) 4 times and O(n/2) extra cost due to loops in the code. So, Recurrence relation for the above code can be written as :- $T(n) = 4T(n/2) + O(n)$ 3 votes 3 votes Shinei Nouzen commented Mar 16, 2019 reply Follow Share $T(n)=4*T(n/2)*T(n/2)+ T(n/2)*T(n/2) + 10*O(n/2))\\ T(n)=(T(n/2)^{2})(4+1) + O(n)\\ T(n)=5T(n/2)^{2} + O(n)$ Why the expression isn't like the one above? 0 votes 0 votes Shaik Masthan commented Mar 16, 2019 reply Follow Share time complexity means howmany times the sub problems are recursively called... after that, you will multiply them for returning the value which takes o(1) times. 2 votes 2 votes Shinei Nouzen commented Mar 16, 2019 reply Follow Share Thanks, got it.. :) 0 votes 0 votes syncronizing commented Mar 16, 2019 reply Follow Share @Shaik Masthan now my doubt is clear, thanks a lot 1 votes 1 votes Devshree Dubey commented Mar 19, 2019 reply Follow Share @Shaik Masthan,Bhai but in above example the code has been used 3 times. However,since 4*T(n/2) has been mentioned therefore,the code used 4 times. Am I right? 0 votes 0 votes Shaik Masthan commented Mar 20, 2019 reply Follow Share noo brother, read one more time the previous comments ! is it 3 times or 4 times used check ome more time ? 0 votes 0 votes Please log in or register to add a comment.