0
$\begingroup$

I have an array with $N$ elements and I run an algorithm that find how many distinct elements are in the array by using a red black tree as follows:

  • for each element
    • if element not in tree
      • insert element to tree
      • increase distinct elements counter by 1

I need to find a formula to count how many comparisons the algorithm performed with $N$ as variable for both the best case and worst case.

For the best case this is pretty easy, the array include $N$ instances of the same element so each search does 1 comparison and there is no insertions, except for the first element, hence the number of comparisons is $N-1$. But I'm having trouble with the worst case. Firstly I'm not sure what is the worst case in this scenario as red black tree balance itself after each insertion, I do know that all the elements in the array must be distinct but in order to get the worst case I will need that each search will go down the longest route to a leaf and same with the insert. How can i devise an input array that cause the worst case and how to create a formula that calculates the max number of comparisons?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.