Running time can be found by solving this recursion. T(sz,target) = SUM {1<=i<=sz} T(i,target-1) T(sz,0) = c
I think it is around O(sz^target) Thanks Nitin On Wed, Aug 3, 2011 at 10:40 AM, aanchal goyal <goyal.aanch...@gmail.com>wrote: > 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 > <goyal.aanch...@gmail.com>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 >> <goyal.aanch...@gmail.com>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 <ankitsamb...@gmail.com>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 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. >>>> >>> >>> >>> >>> -- >>> 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 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.