A cost function is a quadruple (k, b, a, c) standing for
k \cdot b^{\,n} \cdot n^{a} \cdot (\log_2 n)^{c}
Given two of them, f and g, decide how f relates to g and return one of three strings:
"O"— f \in \mathcal{O}(g) but not \Theta(g): the ratio f/g tends to 0;"Theta"— f \in \Theta(g): the ratio tends to a positive constant;"Omega"— f \in \Omega(g) but not \Theta(g): the ratio tends to infinity.
Examples
Input: f = (1, 1, 1, 1), g = (1, 1, 2, 0)
Output: "O"
Explanation: n log n over n^2 tends to 0.
Input: f = (1000, 1, 2, 0), g = (1, 1, 2, 0)
Output: "Theta"
Explanation: the ratio is the constant 1000; constant factors do not count.
Constraints
1 <= k <= 10**6,1 <= b <= 10,0 <= a <= 10,0 <= c <= 10in both quadruples.
Goals
- Tell O, Omega and Theta apart on concrete pairs of functions
- Apply the limit test: the ratio tends to 0, to a positive constant, or to infinity
- See that a constant factor never changes the verdict