Binary search + Sorting vs. Linear search (Big O) [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 1 year ago.

Improve this question

i have a question on a problem i am working on. I have to play Videos randomly in order without repeating a video. Each video is only allowed to be played once per playlist. Each video has an unique id from 0 up to max_video_count which is determined on runtime (depending on the server).

What i do now is, i created a linked list which adds the unique id of each video played. Than i create randomly a random number between 0 and max_video_count , do linear search if the number is already in the linked list and if yes i calculate a new number.. and again linear search .. and so on!!

obvisiouly this isn't very practical and sometimes it takes way to long to find an element. especially when a lot of videos were played already.

So i thought, i implement binear search instead of linear search but that brings me to the problem that i have to sort the list first. So, my next step was to think, that i sort the list while inserting the new unique_id and than do binary search.

I know that binary search is O(log n) compared to O(n) linear search which is a great advancement. But sorting the list is also O(n) because to find the right spot i would have to do linear search again..... So i come to the solution than that binary search would be O(log N * n) compared to O(n) linear search -> linear search fast. Is that right? Maybe my whole approach is wrong.. but i couldn't come up with something better yet...

I am quite new to algorithms so it would be nice if someone could enlighten me here :-)

Greetings Markus

Answer 1

You are essentially just looking at a random permutation. Arrange your videos in one fixed list, and then, to create the playlist, produce a random permutation of that list and play the permuted list.

A typical and efficient (O(n)) way to achieve such a permutation is via a Knuth Shuffle.

_{(Practically, you can of course just create a random permutation of an index set and play the items in order of the permuted indices.)}

Answer 2

If the number of videos is fixed, you could just use an array of booleans, all initialized to false, to keep track of what have been played - constant time lookup. Or use integers, counting number of times played, if you want to limit the number of times instead.

If videos are removed from (or added to) the list over the course of playing, an associative array (in some languages called a dictionary or a hash) for keeping track of what has been played is probably easier.

Don't implement the structure yourself (unless that is the learning exercise you want), use what your language of choice has to offer.