sorry, *target=45*, not sum. sum=0 when we call the function the first time.
On Wed, Aug 3, 2011 at 10:39 AM, aanchal goyal <[email protected]>wrote: > @ Ankit Sambyal, > please explain me why is it O(n^2) taking into account what the number of > times solve is called (in my example above.) > > > On Wed, Aug 3, 2011 at 10:36 AM, aanchal goyal > <[email protected]>wrote: > >> let sum=45 >> int arr[]={1,2,3,4,5}; /*43545 times the function solve is called*/ >> /*2611 ways of achieving the sum (2611 ways >> will be printed)*/ >> >> if, >> int arr[]={1,3,10,30,75}; /*2931 times the function solve is called*/ >> /*53 ways of achieving the sum*/ >> >> >> So, ho here n=5, but see how many times the solve function is called! if >> it was n^2, then it would have been called just 25 times >> >> On Wed, Aug 3, 2011 at 9:55 AM, ankit sambyal <[email protected]>wrote: >> >>> @Ravinder : Its not a DP problem.. If it was, where are the sub problems >>> reused or in other words, where is memoization ?? >>> >>> @Anchal : Its complexity is O(n^2). Look at the following segment in ur >>> code : >>> >>> for(int i=index[n];i<sz;i++) >>> { >>> index[n+1]=i; >>> solve(index,arr,target,cursum+arr[i],n+1,sz); >>> } >>> >>> Here sz is the number of elements in the array i.e. n for complexity. >>> There is a recursive call to solve ...... >>> I hope its clear now . >>> >>> -- >>> 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. >>> >> >> >> >> -- >> Regards,* >> Aanchal Goyal*. >> >> > > > -- > Regards,* > Aanchal Goyal*. > > -- Regards,* Aanchal Goyal*. -- 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.
