Landau symbol

When you keep adding integers infinitely, O (not Zero) is usable to express this difficulty. It is called Landau symbol.

O(n), O(n^2), O(nlogn)

This is expansion anyway.

Traveling salesman problem is well known as Landau symbol.





In this case, there are 4 places. The salesman starts from A and comes back to the same place. He must choose the fastest. This is easy one. However, when you keep adding places, the salesman would be confused.

It is said that there are (n-1)!/2 choices.

If you have 10 places, (10-1)!/2=(9*8*7*6*5*4*3*2*1)/2=181440. There are 181440 choices.
If you have 14 places, (14-1)!/2=3113510400.

This is expansion.

Max=T(1)

k=2
T(k)＞T(1)
Max=T(k)

k＜n and T(k+1)=T(n)＞T(k)
Max=T(k+1)=T(n)


∴