Let's try to split complexity O(NlogN) to 2 part - find solution from the end))...
1. Approach. Let think about problem in next way foreach a[i] we try to find pair (b[j], c[k]) which is so that a[i]+(b [j]+c[k])=0 In this case we need O(n) for cycle a[i] and T(n) for finding out j and k. Can we find b[j]+c[k] = -a[i] (a[i] is fixed on this step) with T(n)= O (log n)? No, we can't, as i understand. We need to perform at least N steps for checking all b[j], so O(n) is necessary and as shown early it's completly enough. That's why T(n) = O(n). So, this approach is a bad idea. We have no time to simple iterating a [i]. But: if there is way to perform O(N logN) preprocessing and then use it for for finding b[j] and c[k] in O(logN), it will be awesome and very beautiful solution!! 2. Propose other splittings /* * write your idea here */ I think algo with O(N log N) preprocessing and O(logN) can be created, so i will think about it. On 30 окт, 13:53, ankur aggarwal <ankur.mast....@gmail.com> wrote: > Given 3 randomly filled array of size N ( say A<a1,a2..aN> , B<b1,b2...bN> and > C<c1,c2..cN> ).give Algorithm to verify if there exists a triplet such that > ai + bj + ck =0 where > 0<I,j,k<=N Time complexity of Your algorithm should be O(NlogN) and state > space complexity of > you're algorithm .O(N^2) algorithm will get partial credit. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
