It is essential to estimate the relative growth rates on the usage of computational time and/or memory space used by the program in order to secure a better performance to do the task.
Before explaining the rules, we need to define the following terms:
Big-Oh: \(T(N) = O(f(N))\) if there are positive constants \(c\) and \(n_0\) such that \(T(N) \le cf(N)\) when \(N \ge n_0\).
Big-Oh commonly indicates the running time of the algorithm in the worst case scenario. It defines the upper bound running time for the algorithm.
Omega: \(T(N) = \Omega(g(N))\) if there are positive constants \(c\) and \(n_0\) such that \(T(N) \ge cg(N)\) when \(N \ge n_0\).
Omega commonly indicates the running time of the algorithm in the best case scenario. It defines the lower bound running time for the algorithm.
Theta: \(T(N) = \Theta(h(N))\) if and only if \(T(N) = O(h(N))\) and \(T(N) = \Omega(h(N))\).
Theta commonly indicates the running time of the algorithm in average case scenario. Usually, this is the realistic running time for the algorithm.
little-oh: \(T(N) = o(p(N))\) if \(T(N) = O(p(N))\) and \(T(N) \not = \Theta(p(N))\).
Little-oh is basically a more strict version of Big-Oh.
Rules
There are rules to be complied when dealing with relative growth rates.
First rule: If \(T_1(N) = O(f(N))\) and \(T_2(N) = O(g(N))\), then
- \(T_1(N) + T2(N) = \text{ max}(O(f(N)), O(g(N))\),
- \(T_1(N) \times T_2(N)= O(f(N) \times g(N))\)
Second rule: If \(T(N)\) is a polynomial of degree \(k\), then \(T(N) = \Theta(N^k)\)
Third rule: \(log^k N = O(N)\) for any constant \(k\). This tells us that logarithms grow very slow.
Ranking
See Growth Rates Ranking#