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 <[email protected]>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
> <[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.
>
--
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.
