ck will be changed every time for your example there will be at most N ck, and so the inner loop will be executed for at most O(N) time.
when there is no available ck, the inner loop will exit On Tue, Nov 3, 2009 at 12:45 PM, dinesh bansal <[email protected]> wrote: > I think this algorithm is O(N^3) because in a worst case when condition > "if(ai + bj + ck > 0)" fail for all the elements in C, the inner loop will > run for N^3 times since we have not incremented j yet. > > lets take a very rough example , A = {1,2,3,4,5}, B = {2,3,4,5,6}, C = > {7,6,5,4,3}, the condition check "if(ai + bj + ck == 0)" will execute for > 5^3 times. > > Thanks, > > On Sun, Nov 1, 2009 at 2:04 PM, daizi sheng <[email protected]> wrote: >> >> 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. >> >> > > > > -- > Dinesh Bansal > The Law of Win says, "Let's not do it your way or my way; let's do it the > best 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.
