RE: What’s the runtime of bubble sort?
The runtime complexity of Bubble Sort is O(n^2) in any average or worst-case scenario, where n is the number of items being sorted. This means if you're doubling the amount of items you need to sort, the time it takes Bubble Sort to finish will roughly quadruple (2^2 = 4). This is because for each item in the dataset, you compare it to every other item. However, in the best-case scenario (where the input is already sorted), Bubble Sort performs at O(n) time complexity. This linear runtime is due to the fact that the algorithm only needs to make one pass through the data set to confirm it's sorted. Also, do note that while Bubble Sort is a simple sort algorithm to understand and implement, its high time complexity makes it impractical for large datasets. There are other sorting algorithms such as QuickSort, MergeSort, or HeapSort that perform better for a larger input size.