View source for Complexities of Basic Sorting Algorithms ← Complexities of Basic Sorting Algorithms


{|class="wikitable" style="text-align: center; color: black;"
! align="left"| Algorithm
! Worst Case
! Average Case
! Best Case
|-
|Bubble
|$\theta(n^{2})$
|$\theta(n^{2})$
|$\theta(n^{2})$
|-
|Selection
|$\theta(n^{2})$
|$\theta(n^{2})$
|$\theta(n^{2})$
|-
|Insertion
|$\theta(n^{2})$
|$\theta(n^{2})$
|$\theta(n)$ \n(when array is sorted)
|-
|Quick
|$\theta(n^{2})$ (when array is sorted, and pivot taken from one end)
|$\theta(nlgn)$
|$\theta(nlgn)$
|-
|Merge
|$\theta(nlgn)$
|$\theta(nlgn)$
|$\theta(nlgn)$
|-
|Heap
|$\theta(nlgn)$
|$\theta(nlgn)$
|$\theta(nlgn)$
|}

[[Category: CS Notes]]
[[Category: Algorithms & Data Structures]]
Algorithm	Worst Case	Average Case	Best Case
Bubble	$\theta(n^{2})$	$\theta(n^{2})$	$\theta(n^{2})$
Selection	$\theta(n^{2})$	$\theta(n^{2})$	$\theta(n^{2})$
Insertion	$\theta(n^{2})$	$\theta(n^{2})$	$\theta(n)$ \n(when array is sorted)
Quick	$\theta(n^{2})$ (when array is sorted, and pivot taken from one end)	$\theta(nlgn)$	$\theta(nlgn)$
Merge	$\theta(nlgn)$	$\theta(nlgn)$	$\theta(nlgn)$
Heap	$\theta(nlgn)$	$\theta(nlgn)$	$\theta(nlgn)$