[Math] Finding best case, worst case, and average case for an unknown algorithm

algorithmscomputer science

I have been given a paragraph explaining what an unknown algorithm does:

An algorithm checks to see if a list of integers is sorted, it starts at the beginning of the list, and scans along until a successive pair of elements is out of order. In this case, the algorithm returns false. In other cases(i.e. the list of integers is sorted) the algorithm would return true.

I have worked out that the worst case running time for this algorithm on an input list of n elements O(n). The best case running time for this algorithm on an input list with n elements is Ω(2). What would be the average-case expected running time be for an input list with a random permutation of numbers from 1,2…n? I'm really not sure if my answers are correct or not…

Best Answer

If the list is uniformly distributed, its $k$ first elements are ordered increasingly with probability $1/k!$ and they are ordered decreasingly with probability $1/k!$ hence the number $N$ of comparisons needed by the algorithm is such that $P[N\geqslant k]=2/k!$ for every $2\leqslant k\leqslant n-1$. Thus, for every $n\geqslant3$, one sees that $2\leqslant E[N]\leqslant2\mathrm e-3$, in particular $E[N]=\Theta(1)$.

Related Solutions

[Math] Worst case complexity of the quicksort algorithm

Typical implementations of quicksort don't append the pivot to one of the lists. Instead, they are implemented (in Haskell notation) as

qsort [] = []
qsort xs = qsort left ++ [pivot] ++ qsort right
    where pivot = head xs
          left  = filter (<x)  xs
          right = filter (>=x) xs

which keeps the symmetry between the left and right lists (if the list elements are distinct) and results in the same number of comparisons for an initial list that is sorted increasing or sorted decreasing.

Note that the 'worst case' isn't just found for the lists that are sorted in increasing or decreasing order. For example, the following lists all require six comparisons to sort:

[1,2,3,4]
[1,2,4,3]
[1,4,2,3]
[1,4,3,2]   
[4,3,2,1]
[4,3,1,2]
[4,1,2,3]
[4,1,3,2]

In general, any ordering which results in the lest or greatest element being selected as the pivot at every stage of the recursion will give you worst case performance.

[Math] Monte Carlo algorithm that determines if a permutation of the integers 1 through $n$ has already been sorted.

How about this: Select $i$ uniformly from $1\ldots n-1$, and then $j$ uniformly from $i+1\ldots n$, so we have $i<j$.

Now check if $a_i < a_j$. If not, we can be sure that the elements of the permutation are not sorted; halt. But if $a_i < a_j$, we are still unsure.

In a random permutation, we will have $a_i < a_j$ with probability $\frac12$. So if we run the algorithm for $k$ steps, and we are still unsure, then we have $2^{-k}$ confidence that the permutation is sorted and not random.

Best Answer

Related Solutions

[Math] Worst case complexity of the quicksort algorithm

[Math] Monte Carlo algorithm that determines if a permutation of the integers 1 through $n$ has already been sorted.

Related Question