Consider n = 5. Naming the array elements as a1,a2,a3,a4,a5 , the final
required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1.
That is nothing but the pattern of a binomial expansion. Using this method,
the complexity can be reduced to O(n).
Correct me if I'm wrong!
On Tue, Apr 9, 2013 at 1:51 PM, Shashwat Kumar <shashwatkmr....@gmail.com>wrote:
> Recursion and iteration don't differ in this algorithm. But avoid using
> recursion if same can be done using iteration. In practical cases, system
> does not allow very large depth in recursion. So for large values of n,
> there can occur segmentation fault.
>
>
> On Tue, Apr 9, 2013 at 11:43 AM, rahul sharma <rahul23111...@gmail.com>wrote:
>
>> If you have any other solution ..please post that...i thnik recursion is
>> ok with base case...we need to scan again after first iteration...??
>>
>>
>> On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma
>> <rahul23111...@gmail.com>wrote:
>>
>>> i forgot to add base case..can add wen 2 elemnts are there then there
>>> sum is stored and we reurn from there...i m in hurry,,,sry for that,,
>>>
>>>
>>> On Wed, Apr 10, 2013 at 12:11 AM, Don <dondod...@gmail.com> wrote:
>>>
>>>> It is O(N^2) because the inner loop takes N steps to execute and that
>>>> loop will be executed N times.
>>>>
>>>> However, I would suggest not using recursion. There is no reason to
>>>> not do it iteratively. Your recursive solution has no base case so it
>>>> will recurse until your computer runs out of stack space, at which
>>>> point it will crash.
>>>>
>>>> Don
>>>>
>>>> On Apr 9, 2:29 pm, rahul sharma <rahul23111...@gmail.com> wrote:
>>>> > A = {5, 3, 8, 9, 16}
>>>> > After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
>>>> > After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
>>>> > Given an array, return sum after n iterations
>>>> >
>>>> > my sol/
>>>> > void abc(int arr[],n)
>>>> > {
>>>> > for(i=0;i<n;i++)
>>>> > arr[i]=arr[i+1]-arr[i];
>>>> > abc(arr,n-1);
>>>> >
>>>> > }
>>>> >
>>>> > I wana ask that the complexity is o(n) or o(n)2......as loop is
>>>> executed n
>>>> > times..say n is 10...so fxn is called 10 times....i.e 10 n..and
>>>> ignoring n
>>>> > it comes out to be...n......but if we implemeted with 2 loops then
>>>> > complexity is n2 ...and both sol are taking same no of
>>>> iterations...please
>>>> > tell whether complexity is n or n2 for above code....if it is n2 then
>>>> how???
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>>
>>>>
>>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> Shashwat Kumar
> Third year Undergraduate student
> Department of Computer Science and Engineering
> IIT Kharagpur
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
Regards,
Shachindra A C
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
