@Sanjay: Shashank was just reiterating what I said in http://groups.google.com/group/algogeeks/msg/8590f8a2a8408d93. The algorithm Shashank described is what I had previously provided code for in http://groups.google.com/group/algogeeks/msg/735671f6a1e16eec, with a correction in http://groups.google.com/group/algogeeks/msg/6b064081b7ba86f0. As far as determining the complexity, you can see that both the while loop and the for loop in my code iterate approximately log_2(quotient) times, which is what makes the code O(log(quotient)).
Dave On Aug 19, 6:46 am, 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.
