IGNOU BCA 4th sem Solved Assignment - Explain the terms Average case

Explain the terms Average case

Ans

Let's say we want to analyze running time of algorithms. Sometimes we say that we want to find the running time of an algorithm when the input size is n and for the worst possible case it is denote it by O(n). Sometimes though I see books/papers saying that we need to find the expected time of an algorithm. Also sometimes the average running time is used .

The average case run time of Quick sort is O(nlogn). Proving this is really a bit much for this course, but we present the proof here for the curious:

• Assume a strategy for choosing pivots such that, after partitioning A into A1 and A2, all lengths of A1 from 0 to |A|-1 are equally likely.

• The running time of quickSort equals the time of its two recursive calls plus time to do the partition.

• pivotIndex is O(last-first).

Suppose that we partition n elements into sub-arrays of length i and (n-i).

Time T to sort the n elements is then:

T(n)=T(i)+T(n-i)+c⋅n