Big O Notation
Objective: Explain Big O
Big O Notation is a way of representing just how long an algorithm takes to execute. It can determine the efficiency of different approaches in solving a problem using sorting and search algorithms. Types of Big O Notation:
O(1): Constant Time Complexity (Best case scenario)
Always take the same amount of time to be executed
O(n): Linear Time Complexity (How long your list is)
The time to execute the algoritm is proportional to the input size of n. The time to run increases as input size of n increases.
O(log n): Logarithmic Time Complexity (Binary Search)
Takes a divide and conquer aproach. Splits the set in half, identifies which size has n then takes that side and repeats. Can only be done with a sorted list.
O(n^²): Quadratic Time Complexity (Bubble Sort)
Bubble sort works by repeatedly traversing a list swapping list positioning where needed on each pass. This can be seen in the form of nesting or nested loops where multiple passes through the list will continue until the list has been sorted. As you can imagine this is not the best approach.
O(n log n): Merge Sort
Merge sort works in a similar approach to binary with a divide and conquer dividing the array in a temporary arrays and reformating and rebuilding the arrays in order.
If you want to go deeper into Big O, check out bigocheatsheet
