Orders of Complexity

I wish I had this table back in 1984 when I was trying to understand this stuff.

Big O Notation Name Example(s)
O(1) Constant # Odd or Even number,
# Look-up table (on average)
O(log n) Logarithmic # Finding element on sorted array with binary search
O(n) Linear # Find max element in unsorted array,
# Duplicate elements in array with Hash Map
O(n log n) Linearithmic # Sorting elements in array with merge sort
O(n2) Quadratic # Duplicate elements in array (naïve),
# Sorting array with bubble sort
O(n3) Cubic # 3 variables equation solver
O(2n) Exponential # Find all subsets
O(n!) Factorial # Find all permutations of a given set/string

and I now can firmly feel the difference between polynomial and exponential well worth this example:

n = 10 | 100 | 1000

n^2 = 100 | 10000 | 1000000

k^n = k^10 | k^100 | k^1000

Paul Baran: Distributed Networks

In 1962, U.S. authorities considered ways to communicate in the aftermath of a nuclear attack. How could any sort of “command and control network” survive? Paul Baran, a researcher at RAND, offered a solution: design a more robust communications network using “redundancy” and “digital” technology.

Rand Corp
Continue reading “Paul Baran: Distributed Networks”