There are three main notations to describe time complexity:
Big-O ("Big-Oh")
Big-Ω ("Big-Omega")
Big-ϴ ("Big-Theta")
Big-O notation provides an upper-bound on the number of operations performed
Big-Ω provides a lower-bound
Big-ϴ provides both an upper-bound and a lower-bound. In other words, Big-ϴ implies both Big-O and Big-Ω.
For our purposes, we will only consider Big-O notation because, in general, we only care about upper-bounds on our algorithms.
- "Constant Time" = O(1)
- "Logarithmic Time" = "Scales/Increases Logarithmically" = O(log n)
- "Polynomial Time" = "Scales/Increases Polynomially" = O(nk) (for any constant k)
- "Exponential Time" = "Scales/Increases Exponentially" = O(kⁿ) (for any constant k)
- "Factorial Time" = O(n!)
Below is a plot of various common time complexities, and it should be clear why the "bad" time complexities are considered so "bad".
Computational problems: P, NP, NP-Hard, and NP-Complete.
int a; // this variable can range from -2³¹ to +2³¹ - 1
long b; // this variable can range from -2⁶³ to +2⁶³ - 1
char c; // this variable can range from -2⁷ to +2⁷ - 1
unsigned int a; // this variable can range from 0 to +2³² - 1
unsigned long b; // this variable can range from 0 to +2⁶⁴ - 1
unsigned char c; // this variable can range from 0 to +2⁸ - 1
