Complexity

Complexity is the way we rank the effectiveness of different data structures and algorithms. We are generally concerned with two types of complexity, time and space. Time complexity measures the amount of time an algorithm takes. Space complexity measures how much memory an algorithm uses.

Big O Notation

Big O Notation is a tool that allows us to generalize the complexity of an algorithm as a function of its input size. For time complexity, the ratio between the size of the input and the amount of time it takes that algorithm to complete on a growing input tells us the effectiveness of that algorithm. The same goes for space complexity and the increase in memory required to complete algorithms. Some examples include (from fastest to slowest):

• Constant - O(1) No change in run time
• Logarithmic - O(log(n))
• Linear - O(n)
• Quadratic - O(n^2)
• Exponential - O(2^n)
• Factorial - O(n!)

Logarithms

Logarithms in computer science are defined by the following equation:

log(N) = y if 2^y = N

As opposed to normal logarithms in in math which default to base 10, we default to base 2. This basically means that as in the input size doubles, it only increases by one unit. Linear time would double as the input doubles.

When an algorithm takes the input and divides it repeatedly in some way, it is best to think about logarithmic complexity. Trees for example are often traversed down one half of the tree and its corresponding branches.