Time Complexities

Time Complexities

For a modern computer, here are the largest sample sizes that can be run in one second for a given time complexity. In this course, most problems will require you to use an algorithm with that time complexity or better.

$n$	Time Complexity
$10$	$\mathcal{O}(n!)$
$25$	$\mathcal{O}(2^n)$
$300$	$\mathcal{O}(n^3)$
$5,000$	$\mathcal{O}(n^2)$
$50,000$	$\mathcal{O}(n^{1.5})$
$10^5$	$\mathcal{O}(n\times \log n\times \log n)$
$5\times 10^5$	$\mathcal{O}(n\times \log n)$
$10^7$	$\mathcal{O}(n)$