# O(n) algorithm

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 09-28-2005
wu_weidong
O(n) algorithm
Hi all,
I am supposed to design an O(n) algorithm that solves the following problem.

Input: An integer v and 2 sorted arrays A and B, each having n integers.
Output: Yes if and only if there exist i and j such that v = A[i] + B[j].
No if no such i and j exist.

The algorithms I came up with were linear search, which gave O(n^2) and binary search, which gave O(n log n). None gave me an O(n) algorithm.

Thank you.

Regards,
Rayne
• 09-28-2005
Rashakil Fol
Think about the problem some more. They only get harder and you need to get better.

Think about the algorithm that merges two sorted lists.
• 09-29-2005
cwr
See this thread. The question was asked by someone else a few days ago.

I can think of an O(n) method, but you need to make an attempt yourself.
• 09-29-2005
pianorain
Quote:

Originally Posted by cwr
See this thread. The question was asked by someone else a few days ago.

I can think of an O(n) method, but you need to make an attempt yourself.

It's a similar question, but not the same. This one is much easier.
• 09-29-2005
cwr
Well, it took me about 15 seconds to think of an O(n) way for the "harder" version. :P
• 09-29-2005
cbastard
Quote:

Originally Posted by cwr
See this thread. The question was asked by someone else a few days ago.

I can think of an O(n) method, but you need to make an attempt yourself.

Yeah, i posted one similar question like that.in which O(N) was expected.I told them my O(n) soln but they wer not satisfied with that because my soln had approx O(n) space complexity also.Even i posted my soln here but thread was deleted.If you have a better soln then post it
• 09-30-2005
pianorain
Let me guess...they wanted it to run in O(n) time and O(1) space?
• 09-30-2005
cbastard
Quote:

Originally Posted by pianorain
Let me guess...they wanted it to run in O(n) time and O(1) space?

I dont know wat exactly they want but they threw me out after this question after all they r microsoft.they want exceptinal
• 09-30-2005
quzah
It could be that you just can't form complete sentences, and you can't spell to save your life. I mean really, can you imagine trying to parse a memo from this guy? I have a hard enough time reading his posts. Now try to get a clue as to what he's trying to say his code is doing. I mean, it's not like we're going to run out of forum space if you don't use "r" instead of "are".

Quzah.
• 10-02-2005
cbastard
sorry,I forgot that i am posting on forums in which members can read hundreds of lines of code but have hard time to judge simple lingo (a little deviated version of english).I will take care for that next time.
I dont know when you will stop blaming me and answer the question.
>>Well, it took me about 15 seconds to think of an O(n) way for the "harder" version. :P

Well can you take out 50 sec more to answer this question.we will be thankful for your time
• 10-03-2005
itsme86
Please, those grammatical "shortcuts" of yours are not a deviated version of English. All you're doing is misspelling words intentionally. Have a look at:
http://www.catb.org/~esr/faqs/smart-...html#writewell
Particularly the first line:
Quote:

We've found by experience that people who are careless and sloppy writers are usually also careless and sloppy at thinking and coding
Maybe then you'll understand.
• 10-03-2005
cwr
My solution takes O(n) space also, so it's probably the same, or no better than yours.
• 10-04-2005
Rashakil Fol
It's probably past the due date now, so I'll post some C code. Notice how the pointers walk through their arrays in the same manner that they do in mergesort, except that one walks backwards.

Code:

```int is_in_sum(int v, int * A, int * B, size_t n) {     /* Assumes A and B are in ascending order. */     int * Ae = A + n;     int * Bw = B + n;     while (Bw != B) {         -- Bw;         while (*A + *Bw < v  &&  A != Ae) {             ++ A;         }         if (*A + *Bw == v) {             return 1;         }     }     return 0; }```
• 10-05-2005
cbastard
>>1.Arrays were not sorted arrays.So no point of ascending elements.
2.We are supposed to find the pairs(not pair) of indexs.
3.Check the complexity also.
Anyways well tried :)
• 10-05-2005
Rashakil Fol
In wu_weidong's problem, they are sorted, and the output is yes or no. Your problem was a different problem. The complexity of the above code is O(n) with O(1) space usage, and the point of mentioning ascending order is to point out that it's not expecting arrays sorted in descending order.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last