by BehindJava

What is the Time and Space Complexity

Home » datastructures » What is the Time and Space Complexity

In this tutorial, we are going to learn about Time and Space Complexity with Examples.


  • A measure of the performance of an algorithm.
  • An algorithm’s performance depends on

    1. Internal factors: The algorithm’s efficiency, in terms of time required to run.

      • Space (memory storage)required to run.
      • Note: Complexity measures the internal factors (usually more interested in time than space)
    2. External factors: Speed of the computer on which it runs.

      • Quality of the compiler.
      • Size of the input to the algorithm.

Space Complexity

  • The space needed by an algorithm is the sum of a fixed part and a variable part.
  • The fixed part includes space for

    • Instructions
    • Simple variables
    • Fixed size component variables
    • Space for constants Etc..
  • The variable part includes space for

    • Component variables whose size is dependant on the particular problem instance being solved.
    • Recursion stack space Etc..

Time Complexity

  • The time complexity of a problem is

    • The number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm.
  • The exact number of steps will depend on exactly what machine or language is being used.
  • To avoid that problem, the Asymptotic notation is generally used.

Asymptotic Complexity

The measure of time complexity of an algorithm where we disregard certain terms of a function to express the efficiency of algorithm is called asymptotic complexity.