Big O Notations

Complexity Graph

• Constant O(1)
• Logarithmic O(log n)
• Linear O(n)
• Linearithmic O(n log n)
• Quadratic O(n^2)
• Cubic O(n^3)
• Exponential O(2^n)

Time Complexity Notations and Examples

Character	Description	Example Problem
n	Size of the input	Linear Search (searching an array of size n)
k	A specific portion of the input or a constant	String Slicing (slicing a substring of length k)
m	Another input dimension, often used with n	Matrix Operations (on an m x n matrix)
log n	Logarithm of the input size	Binary Search (in a sorted array of size n)
n^2	Square of the input size	Bubble Sort (sorting an array of size n)
2^n	Exponential growth relative to the input size	Subset generation (of a set with n elements)
n!	Factorial of the input size	Permutations (finding all permutations of n items)