# 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

1. 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)`

1. 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))`

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