Big O Notation
An algorithm, simply put, is a set of instructions to a computer to perform a task. Big O Notation is a way to classify algorithms based on the time it takes to run the algorithm or the space necessary to run in the worst case scenario. It measures how an algorithm’s performance will change as the size of its input increases.
Big O Notation includes time complexity and space complexity. An algorithm’s time complexity is the time it takes the algorithm to run the input. An algorithm’s space complexity is the space or memory required by the algorithm to run the input.
You can use different algorithms and data structures when writing software which affects whether your program runs fast or slow and how much data space it takes to run. Big O Notation gives you the ability to compare how different algorithms will perform to determine the best one to use to build your program.
There are a variety of data structures and they include: array, hash, linked list, stack, queue, binary tree, etc.
A few basic complexities for algorithms include:
O(1) Constant time:
Constant time indicates that the algorithm’s run time is not affected by the size of the data input. So regardless of how much a data structure holds, the algorithm will take the same amount of time to run.
ex. Index notation is locating an item in an array by referencing its position by number. If you know an item’s location in an array, using index notation will take the same amount of time to execute whether you’re searching for a name in an array list of 10 names or 10,000 names. So finding name[5] in a list of 10 names will take the same amount of time as finding name[999] in a list of 10,000 names.
O(n) Linear time:
Linear time indicates that an algorithm’s run time is related proportionally to the amount of its data input. So time increases linearly with the size of the input. If a data structure contains a lot of data to run through, it will take a longer run time. If the data structure has less data, it will take less time to complete the run.
ex. Iteration is looking at or going through each item in an array. If you don’t know an item’s location in an array, worst case scenario you may have to iterate through all 10 items in a 10 item array. In a 10,000 item array, you may have to iterate over all 10,000 names before finding the name you’re searching for and this will take longer than searching the 10 item array list.
O(log n) Logarithmic time:
Logarithmic time indicates that an algorithm’s run time grows in proportion to the logarithm of the input size. A quick logarithm refresher, think of logarithms like finding the exponent.
The exponent: 5 to the power of 3 equals 125. The number 5 is the base and 3 is the exponent. The exponent indicates how many times the base will be multiplied.
Expressed as a logarithm we would say: log base 5 of 125 equals 3.
ex. A binary search of an ordered array of numbers or letters is a search by halves. Because the array list is ordered (alphabetized), the search for a name starts in the middle of the array (splitting the array into halves) then determines if the value (first letter of the name) is higher or lower than the one you’re searching for, revealing which half of the array to continue searching for the name. Continue to divide the search area in half until the name is found.
There are many more complexities related to Big O Notation so use this link https://www.bigocheatsheet.com to Big O cheat sheet for quick reference charts and other related links. These complexities can be confusing so I try to relate each one to real world examples.
