The Big O Notation

The Big O Notation allows us to talk about the complextiy of a probelm irrespective of the algorithm.

When measuring the complexity of a problem we always look for the worst case scenario.

There are six levels of time complexity...

1. Constant Complexity - O(1)

The time taken will not grow no matter how much the input grows

2. Logarithmic Time - O(LogN)

The time taken will grow as the input grows but not as fast, for example a Binary Search

3. Linear Time - O(n)

As the problem grows, the time grows correspondingly with it, for example a Linear Search

4. Polynomial Time - O(N^k)

1/2 (N^2 - N) Half of N squared minus N

5. Exponential Time - O(K^n)

Only small problems can be solved in a reasonable amount of time

6. Factorial Time O(N!)

E.g Travelling salesman