 |
| A graph showing a visual representation of the various complexitiesin relations to each other. |
Constant Complexity (also known as O(1)) is a problem where the time taken doesn't grow even if the input size varies. For example an algorithm that finds out if a number is even or odd is O(1) complexity as no matter how large the number is it, the time taken is the same. O(1) complexity doesn't have to be just a single line, ordering the first 15 records of a file for example will take the same amount of time if the file is 15 records long or 150 records long.
Linear Complexity (O(n)) is a problem which will take proportionally more time as the input gets bigger. For example ordering a file, ordering a file with 10 records will be about 5 times faster than ordering a file with 50 records.
Logarithmic Complexity (O(log n)) is a problem which will take longer the larger the input is but not to the extent of O(n). A binary search is a good example as the longer the list is the longer it will take to search but not as long as a Linear Search would take.
Polynomial Complexity (O(nk)) is a problem that takes longer the larger the input is and the increase in time is faster than the increase in n. Polynomial Complexity includes Quadratic Complexity O(n2) and Cubic Complexity O(n3). An example of O(n2) would be shaking hands with everyone in a room. With 2 people only 1 is needed but with 7 people 21 are needed.
Exponential Complexity (O(kn)) are problems where the solution can only be found for small values of n, an example would be the "The Chinese Emperor and The Warlord" the payment picked was the chessboard method which 1 grain of rice was placed on the first square, 2 on second, then 4 on the third etc. As the number of squares increase the time taken to calculate the grains of rice increases exponentially. For small inputs it can be worked out but for larger and larger inputs it can potentially take longer than the Earth is around for
Factorial complexity (O(n!)) are problems that can't be solved in a reasonable amount of time. An example would be the Travelling Salesman Problem, this is still being looked into at how to solve it the most efficiently, however it can be solved by O(kn) if Dynamic Programming is used however that still means that only the smallest versions of the problem can be solved, Quantum Computing will be able to help with these sorts of problems but that's still a way off as it's still in its infancy.
