@dave: actually how did u get the approach to this? I mean why did u have to do the q|=1 in the if(a>=b) condition and q<<=1 always in the loop?
On Fri, Aug 19, 2011 at 1:46 PM, Sanjay Rajpal <[email protected]>wrote: > @Shashank : Would you throw some light on how you determined the complexity > ? > > > *Regards > > Sanju > > Happy to Help :)* > > > > On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank > <[email protected]>wrote: > >> We can use bit logic to reduce the time complexity to O(logn) where n is >> Quotient >> >> Algorithm will be as follow as we know >> >> 1. Left shifting an unsigned number by 1 multiplies that number by 2. >> 2. Right shifting an unsigned number by 1 divides that number by 2. >> >> Therefore the procedure for the division algorithm, given a dividend and a >> divisor . >> core logic will be to left shift (multiply by 2) untill its greater then >> dividend , then continue this routine with the the difference between the >> dividend and divisor and divisor till the point where dividend is less than >> divisor or their difference is zero. >> >> Lets see one example: dividend=23 divisor=3 >> >> then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 <23 >> hence now dividend is 11 and quotient in 4(two time shift operation) now >> again 3,6,12.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only >> 3<5 hence remainder =2 quotient =6+1=7 so answer. >> >> Time Complexity O(logn) Number of bits in Quotient >> >> Correct me if anything wrong >> >> *Thanks >> Shashank Mani >> Computer Science >> Birla Institute of Technology Mesra* >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/VszScC-sOfoJ. >> >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- "People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
