Time complexity
The transformation from T(n) to O(n)
Focus on the number of times the inner code is executed during traversal (need to be calculated)
visual
Complexity O(n) between iterations of a layer
Complexity O(n^2) between two iterations
The time complexity of traversal of two arrays at nm is O(nm).
Common time complexity
| O(1) | O(logn) | O(n) | O(nlogn) | O(n^2) | O(n^3) | O(2^n) |
|---|
Spatial complexity
The amount of memory temporarily occupied by an algorithm during its execution
Common spatial complexity
| O(1) | O(n) | O(n^2) |
|---|
During the execution of the algorithm, the memory occupied by the function is constant, so the space complexity is O(1).
If we need to create a new array of size N, then the space complexity is O(n).
If we need to create an array of size n by n, the space complexity is O(n^2).