Big O Notation

As programmers, we often find ourselves asking the same two questions over and over again :

• How much time does this algorithm need to finish ?
• How much space does this algorithm need for this computation ?

What is Big O Notation ?

Big O Notation gives and upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large

we put n - the size of the input Complexities ordered in from smallest to largest :

• Constant Time : O( 1 ) .
• Logarithmic Time : O( log( n ) ) .
• Linear Time : O( n ) .
• Linearithmic Time : O( n*log( n ) ) .
• Quadric Time : O( n^2 ) .
• Cubic Time : O( n^3 ) .
• Exponential Time : O( b^n ) .
• Factorial Time : O( n! ) .

Big O Properties