The sum of an arithmetic progression:

S_n = n * (a₁ + a_n) / 2

When the common difference (d) in an arithmetic progress is 1, we have a₁ = 1 and a_n = n, then:

S_n = n * (1 + n) / 2 = (n + n²) / 2

Algorithm	Best Case	Worse Case	Average Case
Insertion Sort	n	n2	n2
Quick Sort	n*log(n)	n2	n*log(n)

Algorithm	Average/Worse Case	Best Case
Binary Search (sorted array)	log(n)	1
Binary Search Tree	n	h -> height of the tree