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.
$\begingroup$
$\endgroup$
5
-
3$\begingroup$ Great, good luck! $\endgroup$– Yuval FilmusNov 1, 2016 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, 2016 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_HKNov 2, 2016 at 9:13
-
$\begingroup$ I thought it's not necessary to mention that "How can i do this"! @YuvalFilmus $\endgroup$– Shahab_HKNov 2, 2016 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 FilmusNov 2, 2016 at 9:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Nov 1, 2016 at 23:31
-
$\begingroup$ tnx. it (checking subtractions of x and a) was a good idea! $\endgroup$ Nov 2, 2016 at 9:38