5 votes 5 votes Algorithms algorithms time-complexity + – Rahul Jain25 asked Oct 7, 2016 Rahul Jain25 1.2k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Show 10 previous comments Rahul Jain25 commented Oct 14, 2016 reply Follow Share In the perfect power of 2 there will be only bit that has value 1, hence binary search cannot be used, bcoz we cannot know whether 1 is on left or right, so O(n) for scanning number, hence A must be the answer. 0 votes 0 votes Akriti sood commented Oct 17, 2016 reply Follow Share what to do after finding the bit positions of 1 in both the numbers??will we convert them into decimal and then multiple?? what is the use of finding the bit position of 1?? and is'nt the time complexity O(n2) for multiplying two n- bit numbers because each bit of multiplicant is multiplied with multipier?? 0 votes 0 votes Rahul Jain25 commented Oct 18, 2016 reply Follow Share Since it is a perfect power the answer will have only one bit set. We can add the positon in which bit is set in both numbers and add them to get the resultant bit postion which will be set in the answer which can be done in O(1) time hence O(n) is the answer which is used for scanning number. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes #Booth's algorithm can be used to multiple 2 signed binary numbers. It works by shifting and adding bits. This shifting and adding happens for n(no.bits in multiplicand + no. bits in multiplier). Assuming that adding and shifting takes constant time, we can say that upper bound is O(n). Nithish answered Oct 14, 2016 Nithish comment Share Follow See 1 comment See all 1 1 comment reply cse23 commented Oct 18, 2016 reply Follow Share we can convert binary to decimal in O(n) time for n bit number after that multiply and check for the perfect power of 2 which takes O(1) hence in total its : O(n) for 8 bit number it should be O(1) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes BOOTH Algorithm step 1:i=0 s=0|B (upper n bit| lower n bit) do{ step 2:is(s0)Sh =+A (sh=upper bit as in booth takes only in n bit ,after it gots ASR) step 3:s=s/2; i++ }while(i<=n) for n bit=O(n) but for 8 bit=O(1) please correct me if i am wrong Learner_jai answered Jan 15, 2017 Learner_jai comment Share Follow See all 0 reply Please log in or register to add a comment.