3.1.2 - Comparing Algorithms

Problems with different time complexities

Constant Complexity O(1) - This algorithm takes the same amount of time no matter how big the problem is.

Linear Complexity O(n) - As the size of the problem increases, the time taken to solve the problem grows at the same rate. (Proportional) Less efficient

Logarithmic Complexity O(log n) - As the size of the problem grows, the time take to solve the problem increases, but at a slower rate.

Polynomial Complexity O(nk) - As the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time.

Expotential Complexity O(kn) - As the size of the problem grows, the time taken to solve it grows by larger and larger amounts, Only small size version of these problems can be solved in a reasonable amount of time

Factorial Complexity O(n!) - Even worse than exponential. cannot be solved in a reasonable amount of time.