# Big-O Notation

**Big-O notation** is a form of measuring the algorithmic complexity of a function or algorithm in the worst-case scenario. This can either analyze the maximum amount of possible time or memory space needed to solve a particular problem. Solutions can be refactored or reworked to achieve a more efficient time/space complexity with the help of Big-O notation.

## Common Runtimes

Here are some common runtimes:

Runtime | Name | Description | Use Case(s) |
---|---|---|---|

$O(n^{2})$ | Polynomial/quadratic time (in red) | The time needed is the input size, `n` , multiplied by itself. |
Bubble sort has quadratic time complexity. |

$O(n)$ | Linear time (in blue) | The time needed is proportional to the input size `n` . |
Traversing an array of `n` -size. |

$O(ln(n))$ | Logarithmic time (in green) | The time is a logarithmic function `ln()` of the input size `n` . |
Analyzing the binary search algorithm. |

$O(1)$ | Constant time (in purple) | If the time needed by the algorithm is the same, regardless of the input size. | Accessing an element in an array. |

## Simplifying Big-O Expressions

When determining an expression that characterizes the time or space complexity of an algorithm, an expression may contain multiple terms ( e.g., $O(n) + O(ln(n))$ ). In this situation, it is best practice to drop all of the lower order terms so the big-O notation would simplify into just O(n).

## Python Big-O Practice

The following Python example analyzes the time/space complexity of the `foo()`

function:

def foo(list1, list2):for item in list1:print(f"Outer loop: {item}")for item2 in list2:print(f"Inner loop: {item2}")foo(["Hello", "World"], ["Code", "Ninjas"])

For each item of `list1`

in the outer loop, each item in `list2`

is traversed in an inner loop. The Big-O notation for the `foo()`

function would be $O(n^{2})$.