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