Big-O notation in 5 minutes - The basics

<aside> 💡 Simplified analysis of an algorithm's efficiency

</aside>

• complexity in terms of input size, N
• machine-independent
• analyzed time and space

types of measurement

• worse-case
• best-case
• average-case

general rules

• ignore constants
  • $5n \to O(n)$
• certain terms "dominate" others
  • $O(1) < O(log_n) < O(n) < O(n*log_n) < O(n^2) < O(2^n) < O(n!)$
  • lower order terms get ignored

complexity chart

linear time

for x in range(0, n):
	print x; //O(1)

$N*O(1) = O(N)$

y = 5 (15*20);
for x in range(0,n):
	print x;

total time = $O(1) + O(N) = O(N)$

• as $N$ gets infinitely larger, the time it takes for it to compute $y$ is meaningless