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.

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