1 votes 1 votes suppose a problem A reduces to problem B & reduction is done at $O(n^2)$ time. if the problem is solved in $O(n^3)$ time then what about the time of problem A___?? $O(n^2)$ $O(n^3)$ $O(2^n)$ $O(n^5)$ Algorithms algorithms asymptotic-notation made-easy-booklet + – Hira Thakur asked Aug 14, 2016 • retagged Jun 23, 2022 by Lakshman Bhaiya Hira Thakur 499 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Total problem : step(1) REDUCTION => $O(n^2)$ , and step(2) Solve => $O(n^3)$ T(n) = $O(n^2) + O(n^3) = O(n^3)$ so, 2. $O(n^3)$ dd answered Aug 14, 2016 • edited Aug 14, 2016 by dd dd comment Share Follow See all 6 Comments See all 6 6 Comments reply Hira Thakur commented Aug 14, 2016 reply Follow Share why we adding both and taking max??? can i multiply both complexity and O(n^5) is correct?? please clear my doubt... 0 votes 0 votes dd commented Aug 14, 2016 reply Follow Share just tell me what is the complexity of the following code ? int main() { //loop1 for(int i=0; i< n ;i++) { printf("hie"); } //loop2 for(int i=0;i< n^2 ;i++) { printf("bye"); } return 0; } 1 votes 1 votes Arjun commented Aug 14, 2016 reply Follow Share @Debashish Can we use $\Theta$ here? 0 votes 0 votes dd commented Aug 14, 2016 reply Follow Share Sir, I think we can not guarantee the minimum comlexity of solving(step2). so, can not write overall theta($n^3$). correct me if wrong 2 votes 2 votes Arjun commented Aug 14, 2016 reply Follow Share yes, exactly. 0 votes 0 votes Hira Thakur commented Aug 14, 2016 reply Follow Share understand the concept thnx 0 votes 0 votes Please log in or register to add a comment.