QuickSort Assignment
Uploaded by
munirkandaharihotakQuickSort Assignment
Uploaded by
munirkandaharihotakAnalysis of Quick Sort Algorithm
This assignment explains the time complexity, average behavior, space complexity, and
in-place nature of the Quick Sort algorithm.
1. Best Case Complexity: O(n log n)
The best case of Quick Sort occurs when the pivot divides the array into two nearly equal
halves every time. • The recursion tree has approximately log■n levels because the array
size is reduced by half after every partition.
• At each level, all n elements are processed once during partitioning.
• Therefore, the total work becomes:
n × log■n = O(n log n)
2. Worst Case Complexity: O(n²)
The worst case occurs when the pivot is always the smallest or largest element. This
commonly happens when the array is already sorted or reverse sorted and the first or last
element is chosen as pivot. • Instead of splitting into two equal halves, the array is divided
into one part of size 1 and another part of size n−1.
• This creates n recursive levels instead of log n levels.
• The total work becomes:
n + (n−1) + (n−2) + ... + 1
This series is equal to n(n+1)/2, which simplifies to O(n²).
3. Average Case Complexity
The average case complexity of Quick Sort is O(n log n). Even when the pivot does not split
the array perfectly, most partitions are still reasonably balanced. For example, a 30/70 or
40/60 split still produces a recursion tree whose height is proportional to log n. Because
completely unbalanced partitions are rare in practice, Quick Sort usually performs very
efficiently on random data.
4. Space Complexity
The general space complexity of Quick Sort is O(log n). • Quick Sort is an in-place sorting
algorithm and does not require a second array.
• However, recursive function calls require memory in the call stack.
• In the best and average case, the depth of recursion is log n, so the extra space required is
O(log n).
• In the worst case, if the recursion becomes completely unbalanced, the stack depth can
grow to n, giving O(n) space complexity.
5. Meaning of In-Place Algorithm
An algorithm is called in-place if it sorts or modifies the original data without requiring
significant extra memory. Quick Sort rearranges elements by swapping them directly inside
the original array. Unlike Merge Sort, it does not create additional arrays during the sorting
process. Therefore, Quick Sort is considered an in-place algorithm except for the small
amount of memory used by recursion.
Conclusion: Quick Sort is one of the fastest practical sorting algorithms. Its average and
best case complexity are O(n log n), while its worst case is O(n²). Due to its in-place nature
and low memory usage, it is widely used in computer science and software development.