Learning Functional Programming in Go

Big-Oh notation

Big-Oh notation is frequently used to indicate the relative complexity of algorithms.

It’s used to indicate the order of an algorithm. For example, if we have three algorithms, one O(n), one O(n log n), and one O(n2), the times for various n are:

n	O(n)	O(n log n)	O(n2)
10	10	33	100
100	100	664	10000
500	500	4483	250000
1000	1000	9966	1000000
5000	5000	61438	25000000

 

Let’s assume our unit of measurement is one second per operation. The first line in the table tells us that executing 10 operations takes from 10 seconds for an O(n) algorithm to about 1.5 minutes for a O(n2) algorithm. The last line tells us that executing 5,000 operations would take from 1.4 ...