@Shashank: Hmmm. In the recursive call, you use the variable divisor, but I don't see anything assigned to it.
Furthermore, you don't handle negatives, which accounted for almost half of my code. In addition, you have to shift the divisor left multiple times in each recursive call to align it with the dividend. You have O(log(quotient)) recursive calls, and within each one, you have O(log(quotient)) shifts. Doesn't that make your code O((log(quotient))^2)? Dave On Aug 23, 5:01 am, WgpShashank <[email protected]> wrote: > @Dave , You are right , i mean to say we reduce the number of instruction or > comparisons executed by the program. ,Never Mind here is recursive code for > doing the same , Algorithm is already explained > > #include<iostream> > using namespace std; > > int dividend,divisor,remainder; > > int division(int p,int q) > { > > int quotient=1; > > /*if divisor and dividend are equal then quotient=1*/ > if(p==q) > { > remainder=0; > return 1;} > > else if (p<q) /*if dividend is smaller than divisor then remainder=dividend*/ > { > remainder = p; > return 0; > > } > > while(p>=q) > { > q<<=1; > quotient<<=1; > > } > > /*We have reached the point where divisor > dividend so shift right for one > time so that divisor become smaller than dividend*/ > > q>>=1; > quotient>>=1; > > /*again call division recursively*/ > > quotient+=division(p-q,divisor); > > return quotient; > > } > > int main() > { > cout<<"\nEnter dividend:"; cin>>dividend; > cout<<"\nEnter divisor:"; cin>>divisor; > cout<<"\nQuotient:"<< division(dividend,divisor); > > return 0; > > } > > Time Complexity O(log Quotient) > > *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 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.
