2.3.1 BIG O NOTATIONS STIFDF

Space complexity
Time complexity

Indicates how much time an algorithm takes to solve a problem

Indicates how much memory the algorithm uses

Expresses complexity of algorithm and considers worst case scenario
- Remove all terms except one with largest factor/exponent
- Remove any constants

3n then n

When we happen to choose the input which requires the most time

Constant complexity = O(1) = No matter how big/small the list/input size is, it takes the same amount of time
BEST

Linear complexity = O(N) = As list/input size increases , time taken increases proportionally
Okay/mid

Logarithmic complexity = O(log N) = As input size/list increases, time taken increases at slower rates
Great

Polynomial/quadratic =O(N$^{2}$) = As list/input size increases, time taken increases proportionally to the square of list/input size
Not great

Exponential = O(2$^{N}$) =Each extra input added(from 2 to 3 etc), DOUBLES time taken
WORST

BEST:
CONSTANT
LOGARITHMIC
LINEAR
POLYNOMIAL/QUADRATIC
EXPONENTIAL
WORST

O(1) + O(n) + O(n^2) + O(1)
Becomes O(n^2)

Polynomial = O(N$^2$) = for both

Linearithmic = O(n log N)

Average = Linearithmic
WORST = Polynomial = O(N$^2$)

Linear = O(N) = for both

Logarithmic = O(log N) = for both

Average = constant = O(1)
WORST = Linear = O(N) considers overflow list