@Swathi
You are not counting Stack Space used
and as depth of recursion will be O(N) so SC is also O(N) for your solution
`
On Mon, Jul 18, 2011 at 10:22 PM, Swathi <chukka.swa...@gmail.com> wrote:
> Using recursion we can do in O(1) space complexity and O(n) time
> complexity..
>
> int multiply(int a[], int n, int prevproduct, int i)
> {
> int nextproduct = 1;
> if(i>=n)
> return 1;
>
> nextproduct = multiply(a, n, prevproduct*a[i], i+1);
> printf("i=%d product=%d \n ", i, prevproduct*nextproduct);
> nextproduct *= a[i];
> return nextproduct;
> }
>
>
> int main()
> {
> int a[] = {1,2,3,4,5};
> multiply(a,5,1,0);
> getchar();
> return 0;
> }
>
>
> On Mon, Jul 18, 2011 at 6:15 AM, Dumanshu <duman...@gmail.com> wrote:
>
>> @Hary: thanks, ur code works. Could someone tell me the complexity of
>> the above mentioned code???
>> heres the working version of the same http://ideone.com/fDTfj
>> Its increasing exponentially.. so can we say log_2(n)???
>>
>> On Jul 18, 1:57 am, Dumanshu <duman...@gmail.com> wrote:
>> > are u sure that this code works??? because last time i checked it
>> > didn't.
>> >
>> > On Jul 18, 1:22 am, hary rathor <harry.rat...@gmail.com> wrote:
>> >
>> > ary:
>> >
>> >
>> >
>> >
>> >
>> > > int dividend,divisor,remainder;
>> > > int division(int p,int q){
>> > > int quotient=1;
>> > > /*if divisor and diviend are equal then quotient=1*/
>> > > if(p==q){
>> > > remainder=0;
>> > > return 1;}
>> >
>> > > /*if dividend is smaller than divisor then remainder=dividend*/
>> > > if(p<q){
>> > > remainder=p;
>> > > return 0;}
>> >
>> > > /*shift left till divisor > dividend*/
>> > > while(p>=q){
>> > > q<<=1;
>> > > quotient<<=1;}
>> >
>> > > /*shift right for one time so that divisor become smaller than
>> dividend*/
>> > > q>>=1;
>> > > quotient>>=1;
>> > > /*again call division recurcively*/
>> > > quotient+=division(p-q,divisor);
>> > > return quotient;
>> >
>> > > }
>> >
>> > > int * demo()
>> > > {
>> > > int i;
>> > > long long long long long int multi=1;
>> > > for(i=0;i<a.len;i++)
>> > > {
>> > > multi*=a[i];
>> >
>> > > }
>> >
>> > > for(i=0;i<a.len;i++)
>> > > {
>> > > out[i]=mul[i]/a[i];
>> >
>> > > }
>> > > }- Hide quoted text -
>> >
>> > > - Show quoted text -
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
