:O "the final required sum would be 4C0 * a5 - 4C1 * a4 + 4C2 * a3 - 4C3 * a2 + a1" how ? , did i missed something id yes can you paste the link or explain ?
Thanks Shashank On Wednesday, April 10, 2013 5:09:41 AM UTC+5:30, Shachindra A C wrote: > > 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]<javascript:> > > 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]<javascript:> >> > 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]<javascript:> >>> > 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] >>>> <javascript:>>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] <javascript:>. >>>>> 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] <javascript:>. >>> 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] <javascript:>. >> 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.
