Terminology

  • Time Complexity - Runtime of a program. Talks about the time taken by a program to run.

  • Space complexity - Memory/Space that a program consumes to run.

  • Note: These are the key indicators to determine the performance of an algorithm. And always we must consider readings of time and space complexity for worst case scenario to ensure that algorithm performs well in worst cases.

  • For a program, time and space complexities varies based on use case.
    • Best Case - Big-O is determined considering the Optimistic cases, happy flows.
    • Average case - Big-O in this case is determined by giving reasonable inputs, and observing how your aglorithm performs with the given load.
    • Worst case - Big-O is determined considering Pessimistic cases, all “what ifs” like overloaded inputs/stress, exceptional cases
  • Time and Space complexities are represented using Big-O notation.

Big-O Notations (From best to worst)

  • O(1) - Constant time/space complexity
  • O(log n) - Logarithmic time/space complexity
  • O(n) - Linear time/space complexity
  • O(n log n) - Log-Linear time/space complexity
  • O(n^c) - Quadratic/Polynomial time/space complexity. c is constant.
  • O(c^n) - Exponential time/space complexity. c is constant.

References

  1. Big-O CheatSheet