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












1












$begingroup$


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









$endgroup$








  • 2




    $begingroup$
    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.
    $endgroup$
    – marty cohen
    Jan 23 '16 at 6:22










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










  • $begingroup$
    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.
    $endgroup$
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




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
















1












$begingroup$


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









$endgroup$








  • 2




    $begingroup$
    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.
    $endgroup$
    – marty cohen
    Jan 23 '16 at 6:22










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










  • $begingroup$
    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.
    $endgroup$
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




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














1












1








1


1



$begingroup$


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









$endgroup$




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




    $begingroup$
    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.
    $endgroup$
    – marty cohen
    Jan 23 '16 at 6:22










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










  • $begingroup$
    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.
    $endgroup$
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




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














  • 2




    $begingroup$
    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.
    $endgroup$
    – marty cohen
    Jan 23 '16 at 6:22










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










  • $begingroup$
    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.
    $endgroup$
    – Dan Brumleve
    Jan 26 '16 at 4:29








  • 2




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








2




2




$begingroup$
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.
$endgroup$
– marty cohen
Jan 23 '16 at 6:22




$begingroup$
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.
$endgroup$
– marty cohen
Jan 23 '16 at 6:22












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




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












$begingroup$
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.
$endgroup$
– Dan Brumleve
Jan 26 '16 at 4:29






$begingroup$
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.
$endgroup$
– Dan Brumleve
Jan 26 '16 at 4:29






2




2




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




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










2 Answers
2






active

oldest

votes


















0












$begingroup$

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









$endgroup$









  • 1




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










  • $begingroup$
    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$.
    $endgroup$
    – Dan Simon
    Jan 23 '16 at 6:51










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










  • $begingroup$
    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)$.
    $endgroup$
    – Dan Simon
    Jan 23 '16 at 7:39










  • $begingroup$
    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.
    $endgroup$
    – Dan Brumleve
    Jan 23 '16 at 20:38





















0












$begingroup$

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











$endgroup$













    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












    $begingroup$

    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









    $endgroup$









    • 1




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










    • $begingroup$
      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$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 6:51










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










    • $begingroup$
      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)$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 7:39










    • $begingroup$
      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.
      $endgroup$
      – Dan Brumleve
      Jan 23 '16 at 20:38


















    0












    $begingroup$

    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









    $endgroup$









    • 1




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










    • $begingroup$
      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$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 6:51










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










    • $begingroup$
      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)$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 7:39










    • $begingroup$
      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.
      $endgroup$
      – Dan Brumleve
      Jan 23 '16 at 20:38
















    0












    0








    0





    $begingroup$

    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









    $endgroup$



    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




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










    • $begingroup$
      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$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 6:51










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










    • $begingroup$
      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)$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 7:39










    • $begingroup$
      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.
      $endgroup$
      – Dan Brumleve
      Jan 23 '16 at 20:38
















    • 1




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










    • $begingroup$
      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$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 6:51










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










    • $begingroup$
      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)$.
      $endgroup$
      – Dan Simon
      Jan 23 '16 at 7:39










    • $begingroup$
      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.
      $endgroup$
      – Dan Brumleve
      Jan 23 '16 at 20:38










    1




    1




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




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












    $begingroup$
    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$.
    $endgroup$
    – Dan Simon
    Jan 23 '16 at 6:51




    $begingroup$
    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$.
    $endgroup$
    – Dan Simon
    Jan 23 '16 at 6:51












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




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












    $begingroup$
    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)$.
    $endgroup$
    – Dan Simon
    Jan 23 '16 at 7:39




    $begingroup$
    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)$.
    $endgroup$
    – Dan Simon
    Jan 23 '16 at 7:39












    $begingroup$
    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.
    $endgroup$
    – Dan Brumleve
    Jan 23 '16 at 20:38






    $begingroup$
    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.
    $endgroup$
    – Dan Brumleve
    Jan 23 '16 at 20:38













    0












    $begingroup$

    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











    $endgroup$


















      0












      $begingroup$

      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











      $endgroup$
















        0












        0








        0





        $begingroup$

        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











        $endgroup$



        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.




            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

            Bundesstraße 106

            Image
            Dieser Artikel beschreibt die Bundesstraße 106 in Deutschland. Zur gleichnamigen Straße in Österreich siehe Mölltal Straße. Vorlage:Infobox hochrangige Straße/Wartung/DE-B Bundesstraße 106 in Deutschland Karte Basisdaten Betreiber: Deutschland  Bundesrepublik Deutschland Straßenbeginn: Wismar ( 53° 54′  N , 11° 24′  O 53.900536 11.396875 ) Straßenende: Schwerin ( 53° 36′  N , 11° 24′  O 53.592785 11.404892 ) Gesamtlänge: 40,7 km Bundesland: Mecklenburg-Vorpommern Ausbauzustand: zweistreifig [1] Bundesstraße 106 in Schwerin (Umgehungsstraße) Straßenverlauf Land Mecklenburg-Vorpommern Landkreis Nordwestmecklenburg Ortsumgehung Wismar Wallensteingraben über   Dorf Mecklenburg Wallensteingraben Groß Stieten Bad Kleinen OT Niendorf Bahnstrecke Lübeck–Bad Kleinen Zickhusen Lübstorf Klein Trebbow OT Kirch Stück
            Read more

            Verónica Boquete

            Image
            Verónica Boquete im Trikot der Nationalmannschaft (2013) Personalia Name Verónica Boquete Giadans Geburtstag 9. April 1987 Geburtsort Santiago de Compostela, Spanien Größe 159 cm Position Mittelfeld / Sturm Juniorinnen Jahre Station 2001–2005 Xuventú Aguiño Frauen Jahre Station Spiele (Tore) 1 2005–2008 Prainsa Zaragoza 83 (40) 2008–2010 Espanyol Barcelona 53 (30) 2010 Buffalo Flash 9 0 (9) 2010 Chicago Red Stars 3 0 (1) 2010–2011 Espanyol Barcelona 26 (41) 2011 Philadelphia Independence 13 0 (5) 2011 Energija Woronesch 5 0 (1) 2012–2014 Tyresö FF 39 (14) 2014 Portland Thorns FC 15 0 (4) 2014–2015 1. FFC Frankfurt 23 0 (7) 2015–2016 FC Bayern München 9 0 (0) 2016–2018 Paris Saint-Germain 31 0 (8) 2018 Peking BG Phoenix 2019– Utah Royals FC 0 0 (0) Nationalmannschaft Jahre Auswahl
            Read more

            Ida-Boy-Ed-Garten

            Image
            Die Lage des Ida-Boy-Ed-Gartens, rot markiert Der Ida-Boy-Ed-Garten Der Ida-Boy-Ed-Garten, Blick von der Wakenitzmauer durch das Tor in der Stadtmauer Der Ida-Boy-Ed-Garten ist eine Straße der Lübecker Altstadt. Inhaltsverzeichnis 1 Lage 2 Geschichte 3 Literatur 4 Weblinks Lage | Der etwa 90 Meter lange Ida-Boy-Ed-Garten befindet sich an der nördlichen Spitze der Altstadtinsel, vor dem Burgtor. Die in einem Bogen durch eine Grünanlage hangaufwärts führende Straße verbindet die Wakenitzmauer mit der Burgtorbrücke. Geschichte | Der heutige Ida-Boy-Ed-Garten wurde ursprünglich als Verlängerung der Wakenitzmauer angelegt. 1903 wurde in den erhaltenen Teil der mittelalterlichen Stadtmauer, an dem die Wakenitzmauer bei der Einmündung der Kaiserstraße begann, ein Tor mit einem großen Bogen für die Durchführung der Straße und zwei kleineren seitlichen Öffnungen für Fußgänger gebrochen, um für die neu errichteten Wohnhäuser in diesem Bereich
            Read more