SUM {0<=i<=target} C(sz+i-1,i)
O(2^(sz+target-1))
Thanks
Nitin
On Wed, Aug 3, 2011 at 11:03 AM, Nitin Nizhawan <[email protected]>wrote:
> 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.
