Week09 notes

Complexity

n log(n) is closer to n

In real world applications, $\log(n)$ can never be a very large number.

Max memory supported by a 64 bit computer

Imagine on a 64 bit computer, the maximum supported memory size

$N=2^{64}$, which is $16,777,216 TB \approx 17$ billion billion bytes

Estimated number of stars in the unverse:

$10^{22}$ ~ $10^{24}$, i.e. 10~1000 trillion billion stars

$N = 1,000,000,000,000,000,000,000,000$ stars, or a "1" with 24 zeros

$log_{10} N = 24$, $log_2 N \approx 80$

Estimated number of atoms in the universe

$N = 10^{80}$

$log_{10} N = 80$, $log_2 N \approx 266$

Web

Google's web index is estimated to contain around 400 billion documents in 2020

$N = 400,000,000,000$

$log_{10} N = 11.6$, $log_2 N \approx 38.54$

Complexities of Common Sorting Algorithms

Algorithm		Time Complexity		Worst Space Complexity	In place	Stability
	Average	Best	Worst
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	Y	N
Bubble Sort	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	Y	Y
Insertion Sort	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	Y	Y
Heap Sort	$O(n \log(n))$	$O(n \log(n))$	$O(n \log(n))$	$O(1)$	Y	N
Quick Sort	$O(n \log(n))$	$O(n \log(n))$	$O(n^2)$	$O(n)$ Best $O(\log(n))$	N	N
Merge Sort	$O(n \log(n))$	$O(n \log(n))$	$O(n \log(n))$	$O(n)$	N	Y
Bucket Sort	$O(n +k)$	$O(n +k)$	$O(n^2)$	$O(n)$	N	Y
Radix Sort	$O(nk)$	$O(nk)$	$O(nk)$	$O(n + k)$	N	Y
Count Sort	$O(n +k)$	$O(n +k)$	$O(n +k)$	$O(k)$	N	Y
Shell Sort	$O(n \log(n))$	$O(n \log(n))$	$O(n^2)$	$O(1)$	Y	N
Tim Sort	$O(n \log(n))$	$O(n)$	$O(n \log (n))$	$O(n)$	N	Y
Tree Sort	$O(n \log(n))$	$O(n \log(n))$	$O(n^2)$	$O(n)$	N	N
Cube Sort	$O(n \log(n))$	$O(n)$	$O(n \log(n))$	$O(n)$	Y	Y