In the inner loop, either ck get decreased, or bj get increased, but you know there are at moast n possible ck and n possible bj, so the complexity of the inner loop is at most O(n), plus the outer loop, the whole complexity is O(n^2)
On Sun, Nov 1, 2009 at 4:32 PM, Arun <[email protected]> wrote: > This is O(n^3) because of the goto statement (effectively you have replaced > a loop with goto :) I think. > Instead of neightbor in C, you can do a binary search. > This is what I could think of but it doesnt meet the problem's requiremen - > O(nlgn): > 1) O(n^2logn) with O(1) space:) > Sort all 3 arrays. For each pair of a[i],b[j], binary search for > (0-(a[i]+b[j])) in C to see if its present. > 2) O(n^2) with O(n) space > Same as above, but instead of binary search of 0-(a[1]+b[j]) on C, you put > all elements of C in a hash. > There must be some variation of merge sort to do it in nlgn, but Im not able > to see it :) > On Sun, Nov 1, 2009 at 12:39 AM, daizi sheng <[email protected]> wrote: >> >> with all arrays sorted firstly, if you enumerate ai, bj in ascedning >> order, >> ck will be sure in descending order. >> >> foreach(ai in A) >> ck = largest element in C >> foreach(bj in B) >> AGAIN: >> if(ai + bj + ck == 0) algorithm over >> if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN >> if(ai + bj + ck < 0) continue checking next bj >> >> >> On Sun, Nov 1, 2009 at 3:10 PM, anilkumarmyla <[email protected]> >> wrote: >> > No matter whatever i could think of, I am unable to do better than N^3 >> > >> > @daizi sheng >> > I don't get your algorithm >> > "2. enumerate ai, bj both in ascending order," >> > Will that really help ? In what way ? >> > >> > -- >> > >> > 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]. >> > 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]. >> 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]. > 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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
