title: Binary search + Sorting vs. Linear search (Big O)
body: <p>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).</p>
  
  <p>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!! </p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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...</p>
  
  <p>I am quite new to algorithms so it would be nice if someone could enlighten me here :-) </p>
  
  <p>Greetings
  Markus</p>