# Big O notation

The big O notation describes the complexity of an algorithm. It is a key part of learning how to utilise searching and sorting algorithms in your program. Big O notation shows the worst-case and best-case of an algorithm which we can use to determine the execution time and the memory used.

Memory management is important in developing programs especially for old or cheaper hardware, you dont want to have a program that takes a long time to sort through data while also taking up a lot of memory. The big O notaion may look difficult to understand but it is relatively simple and quick to figure out.

### O(1)

The algorithm will always run and use same time and space no matter it's size becuase it is constant.

### O(n)

A linear increase of performance directly proportional to the size of the data set. if say you were searching for a value which happened to be at the start of an array then it would be a very quick execution, but if the eleement was at the end of an array the execution time would be very long.

```            For (int i = 0 < size of array; i++ ) {
if (element = array[i]) {
return true;
}
return false;
}
```

### O(n²)

Performance is proportional to the size of the input data set. This is very common with nested for loops. if youn were to have more nested for loops it would raise the power.

```            for (inti = 0; i < size of array; i++) {
for (int k = 0; k < size of array; k++) {

}
}
```

### O(log n)

Logarithms particularly found in divide and conquer algorithms like binary search. The following example is an iterative binary search example.

```            low = 0
high = N - 1
while (low <= high) {
value > array[i] for all i < low
value < array[i] for all i > high
mid = (low + high) / 2
if (array[mid] >= value) {
high = mid - 1
}
else {
low = mid + 1
}
return low
}
```