Big-O Notation

By National Institute of Standards and Technology (NIST), the definition of Big-O notation is a "theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. " In essence, an algorithm's big-o notation is determined by how effectively it responds to different input, n. Would the process rate be different if we have 100,000 inputs instead of 10 inputs?

The measure of the execution can be expressed as f(n)=O(g(n)). O function is the order function, f(n) is your algorithm, and g(n) is the function you use to estimate f(n). For example, if you f(x)=n^2+3n-40. As n approaches infinity, the value of (3n-40) does not matter as much as n^2, so we can use n^2 to estimate your f(x). Below are some typical Big-O notations:

• O(1) is the constant time function, where it takes the same amount of time to process any size of inputs. An example of O(1) algorithm is to determine if the binary input in odd or even. 
• O(log n) is very efficient to analyze large inputs. The growth peaks at the beginning the marginal time decreases as you increase the number of inputs. For example, the algorithm takes 1 second to analyze the first 100 times, but only take 2 seconds to analyze the first 1000 items.  An example of O(log n) algorithm is to find an item in a sorted array.
• O(n) is the linear function, where the time is proportional to the size of input. An example of O(n) algorithm is to find an item in a unsorted array.
• O(n^2) is an quadratic algorithm that processes inner loops. An example would be what we learned in class on Thursday - bubble sort.
• O(n^n) is an algorithm whose performance is proportional to the square of the size of inputs. To process each element, it will go through the entire set of data. An example would be merge sort.

--------------------------------------------------------------------------------------------------------------------------

Picture References:
1.https://www.google.com/search?q=big+o+notation&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjKg67hsMXQAhXnslQKHQQHBiQQ_AUICigD#imgrc=C161EKuPr8u7CM%3A
Writing References:
1. https://xlinux.nist.gov/dads/HTML/bigOnotation.html
2. https://justin.abrah.ms/computer-science/big-o-notation-explained.html
3. https://en.wikipedia.org/wiki/Big_O_notation
4. https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

--------------------------------------------------------------------------------------------------------------------------