@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 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.
>
>
--
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.
