Three formulas for algorithm complexity analysis

1 + 2 + 3 + 4 + … +n

From [1]

I feel the above visualization can help us better understand the sum of an arithmetic sequence.

(a_1 + a_n)*n/2, where a1 is the first element and a_n is the last one.

insertion sort algorithm has the complexity of O(n²) as 1 + 2 +3 +… +n = (n+1)*n/2

Sum of 1 + 1/2 + 1/4 +… + 1/(2^(i-1))

From [3]

Quick selection algorithm has the complexity of O(n).

Sum of 1 + 1/2 + 1/3 +… + 1/n

See [2]

See the following Leetcode

1862. Sum of Floored Pairs

Reference

[1]http://kateikyousi.link/2016/12/06/%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97%E3%82%92%E3%82%B0%E3%83%A9%E3%83%95%E3%81%AB%E3%81%97%E3%81%A6%E3%81%BF%E3%82%88%E3%81%86/

[2]https://math.stackexchange.com/questions/3367037/sum-of-1-1-2-1-3-1-n

[3]https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF