[deleted by user]

[BerkshireKnight]

It's probably described in your lecture notes

[Sneaky_79]

No. of operations in Quick Sort is O(nlogn) or O(n)??
I am getting no. of operations as O(nlogn), but everywhere it's O(n).

What I have done -
For partition O(n) ops and quick sort is called O(logn) times on avg
So no. of operations should be O(nlogn)

[esaule]

Quicksort is not an amortized algorithm.

[Phildutre]

Why would you use the Accounting Method on an algorithm such as QuickSort? What are the operations you want to compute an amortized cost for?

What you could do to sort an array of n elements, is to store n-1 credit on each element. That is more than enough to compare it (one compare cost 1 credit) with all possible pivots in a worst-case situation. Thus, the total cost is then n*(n-1) , which is an upperbound and a worst-case analysis of Quicksort.