1.12 Time Complexity
- >It is used to measure how the runtime of a function increases with the size of input. Note that time complexity is not equal to execution time. It is used to calculate how a function will scale, given the number of inputs. Time Complexity for a smaller data/problem can be negligible and not necessary to be optimized. Usually one should invest time in tuning time complexity for larger, time intensive problems or problems that require faster response time. This is a good time complexity chart.
Common Time Complexities in ascending order of their growing time.
- >O(1): Constant time. Time does not increase at all.
- >O(logN): Logarithmic time. When time is increasing logarithmically (grows at inversely proportional rate of N).
- >O(N): Linear time. Time increases linearly with the input size.
- >O(NLogN): Linearithmic time. Logarithmic and Linear time together.
- >O(N**K): Polynomial time. When time increases at N (input) to the power K (constant) times.
- >O(K**N): Exponential time. When time increases at K (constant) to the power N (input) times.
Note: Explaining all time complexities would consume lots of space for this book, you can read more about it here.
- >Similar to time complexity there is also space complexity, it is used to measure how the memory of a function increases with the size of input.