164 Are the Androids Dreaming Yet?
Mathematicians have catalogued the universe of problems into classes rather as biologists have catalogued animals into species. Each problem is examined and put into a genus with a name. Sadly the names are not as readable as the Latin names for animals. For example, ‘nlogn’ is the complexity class of most sorting programs, while traversing a maze typically sits in the class NP or P/POLY. Although the classifications look complex the basis of cataloging is simple, a class name signifies the time needed to solve a problem using the best possible algorithm, and the scale this is measured in is ‘Big O°
Big O
Every problem has a complexity. In mathematics this is expressed using ‘Big O’ notation, where ‘O’ stands for order-of-magnitude. The simplest problems have order 1.
If I am working at my computer on a Word document and I press print, the printer will spring to action and print the document. This problem is of flat complexity, notated O(1). It does not matter how large the file is; one click is all I need. I am, of course, assuming sufficient paper in the printer and ink in the cartridges.
The next complexity class is a linear problem, O(n). For example, walking to the store to buy a pint of milk. The farther the store, the longer the walk. The time needed to get to the store is directly proportional to the distance: if ] am walking, a single step multiplied by the number of steps required to cover the distance.
You might think adding two numbers together is a linear problem — the bigger the number, the harder the problem — but there's a clever trick to speed it up. You can get 10 people to add each column in parallel. They'll need to coordinate when someone ends up with a number larger than ten and has to carry the extra digit but this can be easily solved. A problem gets its classification only once we’ve used the cleverest possible trick to solve it.
Most problems we meet in mathematics are somewhere in between flat and linear but there are some that are much harder. The most common hard problem we come across in our daily lives is sorting. Rather than go through a tedious written description, check out the video link on my website. Sorting without using any spare space requires a bubble sort. This is an example of something that needs n squared operations and, since n squared is the simplest example of a polynomial, it is said to be in the polynomial time, or ‘P’ time classification.
HOUSE_OVERSIGHT_015854