Recent News Big-o NotationThe simplest definition I can give for Big-O notation is this:Big-O notationis a relative representation of the complexity of an algorithm.There are some important and deliberately chosen words in that sentence:relative: you can only compare apples to apples. You can’t compare an algorithm to do arithmetic multiplication to an algorithm that sorts a list of integers. But a comparison of two algorithms to do arithmetic operations (one multiplication, one addition) will tell you something meaningful;representation: Big-O (in its simplest form) reduces the comparison between algorithms to a single variable. That variable is chosen based on observations or assumptions. For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering). This assumes that comparison is expensive. But what if comparison is cheap but swapping is expensive? It changes the comparison; andcomplexity: if it takes me one second to sort 10,000 elements how long will it take me to sort one million? Complexity in this instance is a relative measure to something else.
Come back and reread the above when you’ve read the rest.The best example of Big-O I can think of is doing arithmetic. Take two numbers (123456 and 789012). The basic arithmetic operations we learnt in school were:addition;
subtraction;
multiplication; and
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 isO(log n)orlogarithmic 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); andWorst 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 look-ups are denied to the general public. Or are they? Technically you can reverse look-up 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 isunordered(by phone number anyway).So to find a name given the phone number (reverse lookup):Best Case:O(1);Expected Case:O(n) (for 500,000); andWorst Case:O(n) (for 1,000,000).The Travelling SalesmanThis 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 × 1064
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 TimeAnother 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.O(n), O(n2) etc are all polynomial time. Some problems cannot be solved in polynomial time. 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.Source :Big-o notation explained News Reporter