Describe an $O(N)$ time algorithm for determining if there is an integer in a sequence $A$ and an integer in...












1














Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:



Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.



I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:



if(A[a] + B[b] < x) -> update index a to be a + 1

if(A[a] + B[b] > x) -> update index b to be b - 1

if(A[a] + B[b] = x) -> success


However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.






algorithms asymptotics







share|cite|improve this question


















  • 2




    My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
    – marty cohen
    Jan 23 '16 at 6:22










  • I think you can use radix sort since the range is bounded?
    – Dan Brumleve
    Jan 23 '16 at 6:29










  • Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




    I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
    – Ross Millikan
    Jan 26 '16 at 5:08
















1














Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:



Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.



I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:



if(A[a] + B[b] < x) -> update index a to be a + 1

if(A[a] + B[b] > x) -> update index b to be b - 1

if(A[a] + B[b] = x) -> success


However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.






algorithms asymptotics







share|cite|improve this question


















  • 2




    My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
    – marty cohen
    Jan 23 '16 at 6:22










  • I think you can use radix sort since the range is bounded?
    – Dan Brumleve
    Jan 23 '16 at 6:29










  • Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




    I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
    – Ross Millikan
    Jan 26 '16 at 5:08














1












1








1


1





Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:



Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.



I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:



if(A[a] + B[b] < x) -> update index a to be a + 1

if(A[a] + B[b] > x) -> update index b to be b - 1

if(A[a] + B[b] = x) -> success


However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.






algorithms asymptotics







share|cite|improve this question













Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:



Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.



I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:



if(A[a] + B[b] < x) -> update index a to be a + 1

if(A[a] + B[b] > x) -> update index b to be b - 1

if(A[a] + B[b] = x) -> success


However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.






algorithms asymptotics




algorithms asymptotics






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Jan 23 '16 at 6:13









AlexAlex

2872620




2872620








  • 2




    My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
    – marty cohen
    Jan 23 '16 at 6:22










  • I think you can use radix sort since the range is bounded?
    – Dan Brumleve
    Jan 23 '16 at 6:29










  • Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




    I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
    – Ross Millikan
    Jan 26 '16 at 5:08














  • 2




    My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
    – marty cohen
    Jan 23 '16 at 6:22










  • I think you can use radix sort since the range is bounded?
    – Dan Brumleve
    Jan 23 '16 at 6:29










  • Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




    I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
    – Ross Millikan
    Jan 26 '16 at 5:08








2




2




My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22




My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22












I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29




I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29












Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29






Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29






2




2




I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08




I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08










2 Answers
2






active

oldest

votes


















0














Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.






share|cite|improve this answer

















  • 1




    How can you guarantee only a constant number of collisions in each hash bucket?
    – Dan Brumleve
    Jan 23 '16 at 6:38










  • Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
    – Dan Simon
    Jan 23 '16 at 6:51










  • Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
    – Dan Brumleve
    Jan 23 '16 at 6:57










  • Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
    – Dan Simon
    Jan 23 '16 at 7:39










  • I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
    – Dan Brumleve
    Jan 23 '16 at 20:38





















0














Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.



A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.



Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.






share|cite|improve this answer























    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1623228%2fdescribe-an-on-time-algorithm-for-determining-if-there-is-an-integer-in-a-se%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0














    Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.






    share|cite|improve this answer

















    • 1




      How can you guarantee only a constant number of collisions in each hash bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:38










    • Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
      – Dan Simon
      Jan 23 '16 at 6:51










    • Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:57










    • Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
      – Dan Simon
      Jan 23 '16 at 7:39










    • I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
      – Dan Brumleve
      Jan 23 '16 at 20:38


















    0














    Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.






    share|cite|improve this answer

















    • 1




      How can you guarantee only a constant number of collisions in each hash bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:38










    • Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
      – Dan Simon
      Jan 23 '16 at 6:51










    • Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:57










    • Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
      – Dan Simon
      Jan 23 '16 at 7:39










    • I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
      – Dan Brumleve
      Jan 23 '16 at 20:38
















    0












    0








    0






    Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.






    share|cite|improve this answer












    Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Jan 23 '16 at 6:35









    Dan SimonDan Simon

    739611




    739611








    • 1




      How can you guarantee only a constant number of collisions in each hash bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:38










    • Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
      – Dan Simon
      Jan 23 '16 at 6:51










    • Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:57










    • Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
      – Dan Simon
      Jan 23 '16 at 7:39










    • I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
      – Dan Brumleve
      Jan 23 '16 at 20:38
















    • 1




      How can you guarantee only a constant number of collisions in each hash bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:38










    • Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
      – Dan Simon
      Jan 23 '16 at 6:51










    • Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
      – Dan Brumleve
      Jan 23 '16 at 6:57










    • Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
      – Dan Simon
      Jan 23 '16 at 7:39










    • I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
      – Dan Brumleve
      Jan 23 '16 at 20:38










    1




    1




    How can you guarantee only a constant number of collisions in each hash bucket?
    – Dan Brumleve
    Jan 23 '16 at 6:38




    How can you guarantee only a constant number of collisions in each hash bucket?
    – Dan Brumleve
    Jan 23 '16 at 6:38












    Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
    – Dan Simon
    Jan 23 '16 at 6:51




    Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
    – Dan Simon
    Jan 23 '16 at 6:51












    Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
    – Dan Brumleve
    Jan 23 '16 at 6:57




    Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
    – Dan Brumleve
    Jan 23 '16 at 6:57












    Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
    – Dan Simon
    Jan 23 '16 at 7:39




    Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
    – Dan Simon
    Jan 23 '16 at 7:39












    I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
    – Dan Brumleve
    Jan 23 '16 at 20:38






    I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
    – Dan Brumleve
    Jan 23 '16 at 20:38













    0














    Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.



    A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.



    Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.






    share|cite|improve this answer




























      0














      Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.



      A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.



      Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.






      share|cite|improve this answer


























        0












        0








        0






        Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.



        A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.



        Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.






        share|cite|improve this answer














        Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.



        A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.



        Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 26 '16 at 5:42

























        answered Jan 26 '16 at 4:25









        Dan BrumleveDan Brumleve

        12.1k53787




        12.1k53787






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1623228%2fdescribe-an-on-time-algorithm-for-determining-if-there-is-an-integer-in-a-se%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            -

            Popular posts from this blog

            Berounka

            Image
            Berounka.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Caractéristiques Longueur 139  km Bassin 8 861  km 2 Bassin collecteur Elbe Débit moyen ? Cours Source Confluence de la Mže et de la Radbuza · Localisation Pilsen · Altitude 305  m · Coordonnées 49° 45′ 13″ N, 13° 23′ 24″ E Confluence Vltava · Localisation Prague · Altitude 187  m · Coordonnées 49° 59′ 43″ N, 14° 24′ 04″ E Géographie Pays traversés   République tchèque modifier   La Berounka est une rivière de la République tchèque. Elle porte le nom de Mže depuis sa source en Allemagne près de la frontière jusqu'à sa confluence avec la Radbuza à Plzeň. Elle continue ensuite sous le nom de Berounka jusqu'à sa confluence avec la Vltava, près de Prague. La rivière est une destination prisée pour les amateurs de canoë, qui appréc...
            Read more

            Sphinx de Gizeh

            Image
            Pour les articles homonymes, voir Sphinx. Sphinx de Gizeh.mw-parser-output .entete.egypte-antique{background-image:url("//upload.wikimedia.org/wikipedia/commons/c/cc/Picto_infobox_ancient_Egypt.png")} Site d'Égypte antique Le visage du sphinx de Gizeh. Noms en arabe أبو الهول , Abou al-Hôl Localisation Région Basse-Égypte Coordonnées 29° 58′ 31″ nord, 31° 08′ 16″ est Géolocalisation sur la carte : Égypte Sphinx de Gizeh modifier   Le sphinx de Gizeh est la statue thérianthrope qui se dresse devant les grandes pyramides du plateau de Gizeh, en Basse-Égypte. Sculpture monumentale monolithique la plus grande du monde [ 1 ] avec 73,5 mètres de longueur, 14 mètres de largeur et 20,22 mètres de hauteur, elle représente un sphinx couchant. Réalisée vers -2500, elle serait attribuée à Djédefrê, l'un des pharaons de la IV e  dynastie, représentant son père le pharaon Khéops. Sommaire 1 Étymologie 2 Desc...
            Read more

            Different font size/position of beamer's navigation symbols template's content depending on regular/plain...

            Image
            3 Let's suppose I'd like to divert the navigation symbols template (e.g. in order replace them by the frame numbers, see this bug report ;) I would be facing troubles regarding the font size/position, depending on regular/plain frames, as shown by the following MCE. How could I get rid of these troubles? documentclass{beamer} usetheme{PaloAlto} setbeamertemplate{navigation symbols}{insertframenumber/inserttotalframenumber} begin{document} begin{frame} frametitle{A regular frame} end{frame} begin{frame}[plain] frametitle{A plain frame} end{frame} end{document} beamer header-footer share | improve this question asked Dec 10 '18 a...
            Read more