🔒 Locked

THETA( nlogn) algorithm

Started by _John_Galt_ Apr 13, 2005 at 3:15 PM 7 replies 1.8k views

Original Post

Apr 13, 2005 at 3:15 PM

Can anyone tell me how the following can be acheived Given an arbitrary sequence of numbers , an nlogn algorithm to find if some number in the sequence is repeated

yaroslavd

Apr 13, 2005 at 3:21 PM

I'd think you have to go through every element (O(n)). However, if you quick-sort and then binary search the list, each of those is O(nlogn), I think. Someone please correct me if I'm wrong.

Trap

Apr 13, 2005 at 3:23 PM

Looks like a homework question to me. The answer is so simple i can't give a hint without revealing everything.

_John_Galt_

Author

_John_Galt_

Apr 13, 2005 at 3:25 PM

If u sort the list it can be acheived in O(n) time .. . unsorted can u think of a O(nlgn) algorithm?

_John_Galt_

Author

_John_Galt_

Apr 13, 2005 at 3:27 PM

Trap gimme that hint
And no its no homework

Trap

Apr 13, 2005 at 3:32 PM

Sort it with mergesort (the nlogn part of the algorithm, quicksort doesn't guarantee nlogn) then look for duplicates.

It's theta(nlogn)=theta(nlogn)+theta(n)

It can even be done in theta(n+C) with radix sort.

_John_Galt_

Author

_John_Galt_

Apr 13, 2005 at 3:36 PM

man i was ignoring the sorting from the analysis

Fruny

203

Fruny

Apr 13, 2005 at 3:38 PM

Quote:
Original post by Trap
It can even be done in theta(n+C) with radix sort.

Radix sort is Θ(n.E), where E is the number of digits.

[Edited by - Fruny on April 13, 2005 3:38:49 PM]

Trap

Apr 13, 2005 at 3:50 PM

Right, didn't think before writing this part.

It's theta(n*C) with C=E ;)

[Edited by - Trap on April 13, 2005 4:50:53 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.