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 <[email protected]>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 <[email protected]>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 >> <[email protected]>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 <[email protected]> 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 <[email protected]> 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 [email protected]. >>>> 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 [email protected]. >> 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 [email protected]. > 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
