# Time Complexity and Space Complexity

## Introduction

When we practice LeetCode algorithm problems, we often need to calculate the time complexity and space complexity. We learn how to calculate time complexity and space complexity from a simple case.

## Time Complexity

Calculation principle:

**No bottom-order terms****Ignore coefficients for higher order terms**

Give a few simple examples

- Sorting an unordered array

Assume unordered array of length `n`

An unordered array

`[6,5,1,3,4,2]`

can be assumed for experimentation

- Traverse from position
`0`

to position`n - 1`

, take the minimum value and put it at position`0`

, it takes time`n`

- Traverse from position
`1`

to position`n - 1`

, take the minimum value and put it at position`1`

, it takes time`n - 1`

- Traverse from position
`2`

to position`n - 1`

, take the minimum value and put it at position`2`

, it takes time`n - 2`

- so loop to the last position, it takes time
`1`

The following traversal process

```
Position 0 1 2 3 4 ... (n - 3) (n - 2) (n - 1)
⊢---------------------------------------⊣
Traverse n times min
⊢-----------------------------------⊣
traverse n - 1 times min
⊢-------------------------------⊣
traverse n - 2 times min
⊢---------------------------⊣
traverse n - 3 times min
.
.
.
‖
traverse once min
```

Finally add up the time

`n + (n - 1) + (n -2) + ... + 1`

Sum formula based on arithmetic progression

`n * a1 + n * (n-1) / 2 * d`

convert to

`n * a1 + d / 2 * n^2 - d / 2 * n`

Where `a1`

,`d / 2`

,`d / 2`

are constant coefficients, `n`

is used to calculate

The constants of this formula can also be simplified to

`a * n ^ 2 + b * n + c`

According to the principle of time complexity, do not use the low-order items `b * n`

and `c`

, ignore the coefficient `a`

of the high-order item `a * n ^ 2`

, and get its time complexity as `O(n ^ 2)`

- Dichotomy of sorted array to find elements

Assuming a sorted array `[1,2,3,4,5,6,7,8]`

, find the position of the number `7`

- Get the middle position for the first time
`Math.floor((0 + 7) / 2) = 3`

, judge the number`4 < 7`

, continue to find - Get the middle position for the second time
`Math.floor((3 + 7) / 2) = 5`

, judge the number`6 < 7`

, continue to find - Get the middle position for the third time
`Math.floor((5 + 7) / 2) = 6`

, judge the number`7 == 7`

, find the position`7`

```
Position 1 2 3 4 5 6 7 8
The first time ▲
The second time ▲
The third time ▲
```

The length of the array is 8, and the result can be obtained by using the dichotomy method at most 3 times. We find that `log2(8) = 3`

, so the time complexity is `O(log2(n))`

, usually abbreviated as `O(log( n))`

- Intersection of two sorted arrays
`A`

,`B`

`A`

array length `n`

, `B`

array length `m`

, because the size of `n`

and `m`

cannot be compared, it is impossible to determine which is higher order, so the time complexity is brought with `n`

and `m`

`m`

There are three algorithms

- Traverse all
`A`

, traverse all`B`

, time complexity`O(n * m)`

- Traverse all
`A`

, bisection traverse`B`

, time complexity`O(n * log(n))`

- Double pointer traversal
`A`

,`B`

, time complexity`O(n + m)`

## Space Complexity

Calculation principle:

**Refers to extra space, space used for input and output is not counted**

For a simple example, reverse an ordered array

- The first method: create a new auxiliary array of the same size, traverse the array backwards, insert all the contents into the auxiliary array, and then return the auxiliary array, then the space complexity is
`O(n)`

- The second method: traverse the array, directly swap the numbers of the two pointers at the head and tail, without creating a new auxiliary array, but directly operate on this array, then the space complexity is
`O(1)`

## Expand Learning

The meaning of the optimal solution of an algorithm for a program problem: Except for special declarations, the smallest space is used when the time complexity is optimal first.

## Conclusion

The above is what the I have learned from learning an introductory algorithm video course recently. Simply make a programming study note, and more in-depth algorithm complexity calculation needs to be further studied. The follow-up I will learn and update new content, including some algorithm solutions, leetcode study notes, classic algorithm explanations, etc. If you have any questions, please comment.

## Comments