- Created by: Peter Jones
- Created on: 31-05-10 15:11
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...
Levels of 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