**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.
- Read 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.

- Comments are not evaluated, so they are not considered a program step.
- In the while loop, steps are equal to the number of times the loop gets executed.
- 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(N^{2}).