-1
$\begingroup$

I want to get an algorithm with $\theta(nlogn)$ time complexity that search for two elements in an array of integers, which their sum is equal to $x$ such that x is an integer and $n$ is array size.

$\endgroup$
  • 3
    $\begingroup$ Great, good luck! $\endgroup$ – Yuval Filmus Nov 1 '16 at 21:59
  • 1
    $\begingroup$ I don't see a question here, just a copy-paste of an exercise. This is a question-and-answer site, so you must identify a specific question about the exercise if you want to ask here. What did you try? Where did you get stuck? What are you confused about? Do you have any particular questions about this exercise? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. See also meta.cs.stackexchange.com/q/1284/755. $\endgroup$ – D.W. Nov 2 '16 at 2:05
  • $\begingroup$ I know this is a question-and-answer site but what's your mean from "you must identify a specific question"? yes, this almost is a copy-paste of an exercise; but this problem requires a complete algorithm with mentioned conditions and any incomplete effort is unusable. I had some efforts in order to get an algorithm but all of them was incomplete! Is my incomplete tries is useful for you? There is no confusing part and i don't have any particular questions. Just my efforts was failed. I will delete this post, Thanks... @D.W. $\endgroup$ – Shahab_HK Nov 2 '16 at 9:13
  • $\begingroup$ I thought it's not necessary to mention that "How can i do this"! @YuvalFilmus $\endgroup$ – Shahab_HK Nov 2 '16 at 9:25
  • 1
    $\begingroup$ No, but we usually want to know what are your thoughts and were you got stuck. Otherwise we'd be solving your homework for you, and we don't want to be in that role. $\endgroup$ – Yuval Filmus Nov 2 '16 at 9:27
1
$\begingroup$

Hint. Sort the array. That can be done in $\Theta(n\log n)$ time. Then, for each element, $a$, in the array find out if $x-a$ is in the array. Can you do those searches quickly? If you can do each search in time $\Theta(\log n)$, for instance, then that will add on no more than $\Theta(n\log n)$ to your running time.

$\endgroup$
  • $\begingroup$ tnx. it (checking subtractions of x and a) was a good idea! $\endgroup$ – Shahab_HK Nov 2 '16 at 9:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.