@Sanjay: Just think about doing long division with paper and pencil. Then implement it in binary.
If you look at my code, which was posted and corrected earlier in this thread, you will see that both the while loop and the for loop iterate approximately log_2(quotient) times, log_2(quotient) being approximately the number of bits in the quotient. Dave On Aug 19, 11:10 am, Sanjay Rajpal <[email protected]> wrote: > @Dave : How did you approach this solution to this problem ? > and how you saw that th complexity is O(log_2(Quotient)) ? > > *Regards > > Sanju > > Happy to Help :)* > > > > On Fri, Aug 19, 2011 at 8:44 AM, Dave <[email protected]> wrote: > > @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 inhttp://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. -- 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.
