dimanche 2 février 2020

How to do complexity analysis of this code with the if-else statements?

I'm working on finding out what the complexity of this code is:

///Note: a[i] is an array with n elements

for (int i = 0; i < n; i++) {
  if (Math.random() > 0.25)
       if (i%4 == 0)
        BubbleSort (a[i]);
       else
        QuickSort (a[i]);
  else
   for (int j = i; j < n; j++)
     for (int k = i; k < n; k++)
       BinarySearch (a[i]);
}

from my understanding, bubblesort is n^2, quicksort best case is nlogn but worst case is n^2, and binarysearch is logn but requires the list to be sorted. Going through the code 25% of the time it'll do binary search and the other times it will either do quicksort or bubble sort, and in that section it'll have 1/4 chance of doing bubblesort and 3/4 chance to do quicksort. To find the complexity would I have to make separate equations for the best case and worst case?

Aucun commentaire:

Enregistrer un commentaire