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 <daizish...@gmail.com> 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 <arunm...@gmail.com> 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 <daizish...@gmail.com>
> 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 <anilkumarm...@gmail.com>
> >> 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 algoge...@googlegroups.com.
> >> > 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 algoge...@googlegroups.com.
> >> 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 algoge...@googlegroups.com.
> > 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 algoge...@googlegroups.com.
> 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 algoge...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
