O(n) algorithm

This is a discussion on O(n) algorithm within the C Programming forums, part of the General Programming Boards category; Hi all, I am supposed to design an O(n) algorithm that solves the following problem. Input: An integer v and ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    8

    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.

    Please help.

    Thank you.

    Regards,
    Rayne

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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.

  3. #3
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    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.

  4. #4
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  5. #5
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    Well, it took me about 15 seconds to think of an O(n) way for the "harder" version. :P

  6. #6
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    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

  7. #7
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Let me guess...they wanted it to run in O(n) time and O(1) space?
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  8. #8
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    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

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    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

  11. #11
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,175
    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:
    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.
    If you understand what you're doing, you're not learning anything.

  12. #12
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    My solution takes O(n) space also, so it's probably the same, or no better than yours.

  13. #13
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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;
    }

  14. #14
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    >>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
    Long time no C. I need to learn the language again.
    Help a man when he is in trouble and he will remember you when he is in trouble again.
    You learn in life when you lose.
    Complex problems have simple, easy to understand wrong answers.
    "A ship in the harbour is safe, but that's not what ships are built
    for"

  15. #15
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21