## DEV Community

Bhav Kushwaha

Posted on • Updated on

# QuickSort - Time Analysis (Part2)

## Stating the Fundamentals

1) Suppose we have a simple function to print every item in a list:

``````def print_items(list):
for items in list:
print item
``````

This function goes through every item in the list and prints out.

2) Now consider the same function but with a 1 second sleep() associated with every iteration in it.

``````from time import sleep
def print_items2(list):
for items in list:
sleep(1)
print item
``````

The Key points:

• Both functions loop through the list once, so theoriticaly they both have O(n) time complexity.

• But the print_items() is evidently faster than the latter since it doesn't contains the sleep function and is executed faster.

• So even though both functions are the same speed in Big O notation like O(n), print_items is practically faster.

From the above example we gather:

• When we write Big O notation like O(n), it really means this:

• c is some fixed amount of time that your algorithm takes, called constant.

For Example, it might be 10 ms for print_items and 1 sec for print_items2.

## Example of Binary Search vs Simple Search

Suppose both the algorithms had the following constants:

You might assume Simple Search is way faster due to a very low constant value than Binary Search.

But now considering a list of 4 Billion Elements!

NOTE : Here the constant c doesn't get considered and Binary Search is proved to be more faster.

## QuickSort vs MergeSort Case

In this case the constant associated with the time complexity plays an important role is determining the better performing Sorting Algorithm.

• Quicksort has a smaller constant than Mergesort!

• Sof if they're both O(n) time, then quicksort is faster!

• And Quicksort is faster in practice too, since it hits the average case way more often than the worst case.

## Different Cases of Quicksort

Worst Case

• The performance of quicksort heavily depends on the pivot you choose.

• Suppose you always choose the first element as the pivot, and you call a quicksort on an array that is already sorted.

• Here, quicksort doesn't check whether the array is sorted or not, it will try to sort it again.

• Stack Size in Worst Case: O(n)

Best Case

• Now instrad, suppose you always picked the middle element as the pivot. Look at the call stack now:

• It's so short! Because you divided the array in half everytime, you don't need to make as many recursive calls. You hit the base case sooner and the call stack is much shorter.

• Stack Size in Best Case: O(logn)

Average Case

• Now take any element as the pivot and the rest of elements are divided in sub-arrays. You will get the result exactly same as the best case.

• Stack Size in Average Case: O(logn)

## Something about the Call Stack at every level

• The first operation takes O(n) time since you touched all 8 elements on this level of stack. But actually you touch O(n) elements on every level of the call stack.

• Even if you partition the array differently, you still are touching O(n) elements everytime.

So each level takes O(n) time to complete.

## Conclusion

• We conclude with the above findings that the Height of Call Stack is O(logn) and each level takes O(n) time.

• The entire Quicksort Algorithm will take: `O(n) * O(nlogn) = O(nlogn)`

The Time Complexity of the Best-Case & Average-Case of Quicksort.

• In the Worst-Case, there are O(n) levels, so the algorithm takes `O(n) * O(n) = O(n^2)`

NOTE: If you always choose a random element in the array as the pivot, quicksort will complete in O(nlogn) time on average.

• Quicksort is one of the fastest sorting algorithms out there!