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

            Aardman Animations

            Image
            Aardman Animations, Ltd. Aardman Animations Tipo privada Atividade Animação em stop-motion , Animação em CGI Fundação 1972 Fundador(es) Peter Lord David Sproxton Sede Bristol, Inglaterra  Reino Unido Proprietário(s) Dreamworks Pessoas-chave Peter Lord David Sproxton Nick Park Divisões Aardman Features Aardman Digital Aardman Commercials Aardman Broadcast Aardman International Aardman Rights Aardman Effects Aardman 3-D Systems Aardman Nathan Love AardBoiled Website oficial aardman.com
            Read more

            Are they similar matrix

            Image
            0 $begingroup$ Do $begin{bmatrix} 0&i&0\0&0&1\0&0&0 end{bmatrix} $ and $begin{bmatrix} 0&0&0\-i&0&0\0&1&0 end{bmatrix} $ are similar.Is this True/false Clearly both are nilpotent and one is conjucate transpose of other but how to know if they are similar.i'm stuck. Please help me linear-algebra vector-spaces eigenvalues-eigenvectors generalizedeigenvector share | cite | improve this question edited Dec 10 '18 at 6:38 Vasanth Kris asked Dec 10 '18 at 6:19
            Read more

            “minimization” problem in Euclidean space related to orthonormal basis

            Image
            3 $begingroup$ I have stumbled upon an exercice for second year undegraduate student majoring in economics which I find quite demanding. I have an idea for the solution, but it seems awfully complicated, and I am wondering if there was a simpler way to solve it. This goes as follows: Let $(E, langle, rangle)$ be a euclidean space of dimension $n geq 2$ . 1) For any $x in E$ , show that $||x|| = sqrt{n}$ if and only if there exists $(e_1, dots, e_n)$ an orthonormal basis of $E$ such that $x =e_1+ ldots + e_n$ . 2) For any $(x,y) in E$ , show that $||x|| = sqrt{n}$ , $||y|| = sqrt{frac{n(n+1)(2n+1)}{6}}$ and $langle x,y rangle = frac{n(n+1)}{2}$ if and only if there eixsts $(e_1, ldots, e_n)$ an orthonormal basis of $E$ such that $x = e_1 + ldots + e_n$ and $y = e_1 + 2e_2 + ldots + ne_n$ The first q
            Read more