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

Complexity

• 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.