BigO Time Complexity

Wednesday, January 13th 2016

• Big-0 complexity analysis (time)
• Where n is the number of inputs, what is the relationship between n and time to compute?
• O(1) - Constant
• No matter the number of inputs (1 or 10^100), the function will take the same amount of time to compute. As n grows, time remains constant.
• Eg:
• Looking through an array
• hash table insertion
• O(log(n))

• As the number of inputs (1 or 10^100) grows, time to compute will increase but at a decreasing rate. 
• Eg:
• Binary Search

• O(n) - Linear
• The number of inputs (1 or 10^100) will impact the performance of the function, whether it is 2n, 4n, or 100n, it doesn't matter (the rate of growth is constant). As n grows, time will grow at some constant pace (multiple of n).
• Eg:
• Finding an element in an unsorted array
• O(n^2) - Quadratic
• The time to compute n increases at an increasing rate.
• Eg:
• multiplying two n's using a simple algorithm 
• operations/functions nested within one another
• bubble, shell, selection, insertion sort
•  O(c^n) - Exponential
• Each computation is an order of magnitude(>=10) based on each additional n
• Eg:
• brute force password hacking (each digit could be any number of possibilities)
• brute-force search