# Tag Info

6

Meanwhile knowing how "sorted" an array is gives some information about the array and might help sorting it more efficiently, it is not quite right, that quick-sort runs in $O(n^2)$ if the array is sorted. The running time of quick-sort depends on the pivoting rule and your statement holds only if we always choose the first (or last) element as the pivot. A ...

2

In more detail, this variant of bubble sort finds the leftmost pair of adjacent items that are in the wrong order. Then it swaps those two items. This operation of "find and swap" is repeated until the given list is sorted. In other words, this variant of bubble sort swaps the items in the leftmost inversion of the given list repeatedly until the given list ...

1

The usual rule here is only one question per post. Link [2] doesn't say that random pivot and median pivot lead to $O(n^2)$ time complexity. The median of first, middle, and last element is not the median of the whole array. Writing "median pivot" is probably a bad idea, unless you have carefully specified what that's a median of. Link [1] says that ...

1

You can compute the average using linearity of expectation. Let the random variable $X$ denote the number of elements that are retained. Let $X_i$ be an indicator r.v. that is 1 if the $i$th element is retained, or 0 otherwise. Then $X = X_1+\dots + X_n$, so $$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1].$$ ...

Only top voted, non community-wiki answers of a minimum length are eligible