2 votes 2 votes Algorithms algorithms divide-and-conquer time-complexity ace-test-series + – Parshu gate asked Nov 18, 2017 retagged Jul 8, 2022 by Lakshman Bhaiya Parshu gate 1.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Red_devil commented Nov 18, 2017 reply Follow Share i came up with this way: divide the long int in multiple parts and multiply with the other one T(n)=2T(n/2)+n^2; multiplication have n^2 time complexity a=2;b =2; k=2; so T(n)=O(n^2) 1 votes 1 votes abhi19961 commented Sep 16, 2018 reply Follow Share What i think is, the recurrence would be T(n)=T(n/2)+n^2 +n .The last "n" in the equation is the sum of the all the divided solutions which is O(n). 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes http://www.cs.umd.edu/~meesh/351/mount/lectures/lect10-long-int-multiply.pdf Prateek Raghuvanshi answered Nov 20, 2017 Prateek Raghuvanshi comment Share Follow See all 0 reply Please log in or register to add a comment.