Data Structures

# Mastering Time and Space Complexity – A Comprehensive Guide

## Time and Space Complexity

Time and space complexity are used to measure algorithm efficiency.

## Complexity

• Complexity is a measure of how resource requirements change as the size of the problem gets larger.
• The higher the complexity of the problem, the lower the performance.

## Algorithm Operations

When computing a program, these are the fundamental operations it carries out.

• Arithmetic operations.
• Assignment operations.
• Write operations.
• Test conditions.

## Performance

• Performance is measured along with resource consumption, and code consumes a variety of resources.
• Improving code performance beyond a certain point involves a trade-off.

### Measures of performance

• Time: The amount of processing or number of operations the code has to perform to accomplish its objective.
• Space: Both the disk space and the memory that code needs for persistent storage during runtime.
• Network: The bandwidth code is used to pass information to clients or other machines.

#### Time complexity

time required to analyze a given problem of particular size is known as the time complexity.
Time complexity depends on the following factors:

• Size of input data.
• Hardware.
• Operating system.
• Programming language used.
##### Time complexity depends on two components
• Fixed part: compile time.
• Variable Part: Run time dependent on problem instance. Run time is usually considered, and compile time is ignored.

#### Ways to measure time complexity

Step count: count the number of program steps.

1. Comments are not evaluated, so they are not considered a program step.
2. In the while loop, steps are equal to the number of times the loop gets executed.
3. In a for loop, steps are equal to the number of times an expression is checked for a condition.

## Space Complexity

The amount of memory required to solve a given problem of particular size is called space complexity.
The space complexity  depends on two components:

• Fixed part: It is needed for instruction space. i.e byte code, variable space constant space, etc.
• Variable part: Instance of input and output data.

### Formula

``space(s) = fixed part+ variable part.``

## How do I find complexity??

It depends on the following statements:

• Sequence of statements.
• if-then-else statements.
• for loops.
• Nested loops.

### Sequence of Statements

``````statement 1;
statement 2;
...
statement n;``````

By adding the times for all statements, one can determine the total time.

``total time = time(statement 1) + time(statement 2)+ ...+ time(statement k)``

If each statement is simple, then the time for each statement is constant, and the total time is also constant: O(1).

### if-then-else statements

``````if(condition){
sequence of statements1
}
else{
sequence of statements2
}``````

Here, either sequence of statements1 will execute, or sequence of statements2 will execute. Therefore, the worst-case time is the slowest of the two possibilities: max(time(sequence 1), time(sequence 2)).
Example:
if sequence 1 is O(N) and sequence 2 is O(1), the worst-case time for the whole if-then-else statement would be O(N).

### for loops

``````for (i=0; i<N;i++){
sequence of statements
}``````

The loop executes N times, so the sequence of statements also executes N times.
If we assume the statements are O(1), the total time for the for loop is N*O(1), which is O(N) overall.

### Nested loops

``````for (i=0;i<n;i++) {
for (j=0;j<n;j++) {
sequence of statements
}
}``````

The outer loop executes n times. Every time the outer loop executes, the inner loop executes m times. As a result, the statements in the inner loop execute a total of n*m times. Thus, the complexity is O(n*m).
In some cases where the stopping condition of the inner loop is j<n instead of j<m, the total complexity for the two loops is O(N2).

``````for (i=0;i<n;i++) {
for (j=i+1;j<n;j++) {
sequence of statements
}
}``````

In above example, we can’t multiply the number of iterations of the outer loop times the number of iterations of the inner loop, because the inner loop has a different number of iterations each time.
The number of iterations in a loop can be calculated in following way:

``````Value of i       Number of iterations of inner loop
0                  n
1                 n-1
2                 n-2
-                 ---
n-2                 2
n-1                 1``````

The total number of times the sequence of statements executes is: n+ n-1 + n-2 + … + 3 + 2 + 1. The total is O(N2).

Scroll to Top