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?


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.