Simple Explanation of Big O Part II

So if you want to find a name in a phone book of a million names you can actually find any name by doing this at most 20 times. In comparing search algorithms we decide that this comparison is our 'n'.

For a phone book of 3 names it takes 2 comparisons (at most).
For 7 it takes at most 3.
For 15 it takes 4.
For 1,000,000 it takes 20.

That is staggeringly good isn't it?

In Big-O terms this is O(log n) or logarithmic complexity. Now the logarithm in question could be ln (base e), log10, log2 or some other base. It doesn't matter it's still O(log n) just like O(2n2) and O(100n2) are still both O(n2).

It's worthwhile at this point to explain that Big O can be used to determine three cases with an algorithm:

  • Best Case: In the telephone book search, the best case is that we find the name in one comparison. This is O(1) or constant complexity;
  • Expected Case: As discussed above this is O(log n); and
  • Worst Case: This is also O(log n).

Normally we don't care about the best case. We're interested in the expected and worst case. Sometimes one or the other of these will be more important.

Back to the telephone book.

What if you have a phone number and want to find a name? The police have a reverse phone book but such lookups are denied to the general public. Or are they? Technically you can reverse lookup a number in an ordinary phone book. How?

You start at the first name and compare the number. If it's a match, great, if not, you move on to the next. You have to do it this way because the phone book is unordered (by phone number anyway).

So to find a name:

  • Best Case: O(1);
  • Expected Case: O(n) (for 500,000); and
  • Worst Case: O(n) (for 1,000,000).

The Travelling Salesman

This is quite a famous problem in computer science and deserves a mention. In this problem you have N towns. Each of those towns is linked to 1 or more other towns by a road of a certain distance. The Travelling Salesman problem is to find the shortest tour that visits every town.

Sounds simple? Think again.

If you have 3 towns A, B and C with roads between all pairs then you could go:

A -> B -> C
A -> C -> B
B -> C -> A
B -> A -> C
C -> A -> B
C -> B -> A

Well actually there's less than that because some of these are equivalent (A -> B -> C and C -> B -> A are equivalent, for example, because they use the same roads, just in reverse).

In actuality there are 3 possibilities.

Take this to 4 towns and you have (iirc) 12 possibilities. With 5 it's 60. 6 becomes 360.

This is a function of a mathematical operation called a factorial. Basically:

5! = 5 * 4 * 3 * 2 * 1 = 120
6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
25! = 25 * 24 * ... * 2 * 1 = 15,511,210,043,330,985,984,000,000
50! = 50 * 49 * ... * 2 * 1 = 3.04140932... × 10^64 

So the Big-O of the Travelling Salesman problem is O(n!) or factorial or combinatorial complexity.

By the time you get to 200 towns there isn't enough time left in the universe to solve the problem with traditional computers.

Something to think about.

Polynomial Time

Another point I wanted to make quick mention of is that any algorithm that has a complexity of O(na) is said to have polynomial complexity or is solvable in polynomial time.

Traditional computers can solve polynomial-time problems. Certain things are used in the world because of this. Public Key Cryptography is a prime example. It is computationally hard to find two prime factors of a very large number. If it wasn't, we couldn't use the public key systems we use.


Second part of the explanation.

Folksonomies: computer science algorithms

/technology and computing/consumer electronics/telephones/mobile phones (0.559808)
/technology and computing/hardware/computer/servers (0.448478)
/art and entertainment/music (0.447464)

phone book (0.979238 (negative:-0.365810)), best case (0.876236 (positive:0.288549)), Travelling Salesman problem (0.828563 (neutral:0.000000)), telephone book (0.648936 (positive:0.216043)), telephone book search (0.631523 (positive:0.216043)), reverse phone book (0.628961 (negative:-0.365810)), ordinary phone book (0.628480 (neutral:0.000000)), phone number (0.623111 (negative:-0.252952)), polynomial time (0.618146 (neutral:0.000000)), traditional computers (0.615200 (negative:-0.444007)), public key (0.607847 (negative:-0.306131)), Public Key Cryptography (0.606477 (negative:-0.306131)), public key systems (0.606118 (neutral:0.000000)), towns (0.586400 (negative:-0.166909)), complexity (0.574902 (negative:-0.332790)), logarithmic complexity (0.565379 (neutral:0.000000)), constant complexity (0.557715 (negative:-0.332790)), polynomial complexity (0.542220 (neutral:0.000000)), worst case (0.541152 (negative:-0.772343)), Big-O terms (0.541034 (neutral:0.000000)), search algorithms (0.540054 (positive:0.548944)), Simple Explanation (0.538916 (negative:-0.239408)), polynomial-time problems (0.531086 (negative:-0.280741)), shortest tour (0.529558 (neutral:0.000000)), combinatorial complexity (0.529206 (neutral:0.000000)), general public (0.525882 (negative:-0.540282)), mathematical operation (0.523938 (neutral:0.000000)), famous problem (0.523179 (positive:0.427387)), quick mention (0.523119 (neutral:0.000000)), certain distance (0.521869 (positive:0.357617))

BC:Country (0.853523 (positive:0.332800)), Travelling Salesman:Company (0.767355 (positive:0.552451)), Salesman:JobTitle (0.521897 (neutral:0.000000)), computer science:FieldTerminology (0.442046 (positive:0.427387))

Computational complexity theory (0.949218): dbpedia | freebase
Reverse telephone directory (0.820060): dbpedia | freebase
Telephone numbers (0.770183): dbpedia
Telephone directory (0.714914): dbpedia | freebase | opencyc
Telephone (0.714224): dbpedia | freebase | opencyc
Analysis of algorithms (0.669607): dbpedia | freebase | yago
Travelling salesman problem (0.644805): dbpedia | freebase | yago
Sorting algorithm (0.622977): dbpedia | freebase | opencyc

 Plain English explanation of Big O
Electronic/World Wide Web>Message Posted to Online Forum/Discussion Group:  Unknown, (01/19/2013), Plain English explanation of Big O, Retrieved on 2013-05-29
  • Source Material []
  • Folksonomies: complexity algorithms


    29 MAY 2013

     Big O Continued

    Simple Explanation of Big O Notation > Place/Position > Simple Explanation of Big O Part II
    Linking the two memes into one complete explanation.
    Folksonomies: continuation
    Folksonomies: continuation