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
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)
External factors: Speed of the computer on which it runs.
- Quality of the compiler.
- Size of the input to the algorithm.
- The space needed by an algorithm is the sum of a fixed part and a variable part.
The fixed part includes space for
- 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..
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.
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.