Dependencies

Let \(T f : \mathbb {N} \rightarrow \mathbb {N}\) be functions such that the recurrence

holds for some \(a {\gt} 0\) and \(b {\gt} 1\). Let also \(f(n) \in \Theta (n^d)\) for some \(d \ge 1\). Then the following holds:

1. if \(a {\lt} b^d\), then \(T(n) \in \Theta (n^d)\),

2. if \(a = b^d\), then \(T(n) \in \Theta (n^d \log _b{n})\) and

3. if \(a {\gt} b^d\), then \(T(n) \in \Theta (n^{\log _b{a}})\).

In the case where \(f\) is bounded above by \(n^d\) only above or only below, \(T\) is also bounded only above or only below by the respective function.

\(f\) is asymptotically bounded by \(g\) if \(f\) is asymptotically bounded above and below by \(g\).

\(f\) is asymptotically bounded above by \(g\) if there exists a \(k {\gt} 0\) such that \(f\) is asymptotically less than \(k*g\).

\(f\) is asymptotically bounded below by \(g\) if there exists \(k {\gt} 0\) such that \(f\) is asymptotically greater than \(k*g\).

\(f\) is asymptotically greater than \(g\) if there exists \(x_0\) such that \(f(x) \ge g(x)\) for all \(x \ge x_0\).

\(f\) is asymptotically less than \(g\) if there exists \(x_0\) such that \(f(x) \le g(x)\) for all \(x \ge x_0\).

\(f\) asymptotically dominates \(g\) if for all \(k {\gt} 0\) \((x)\) is asymptotically greater than \(k*g\).

\(f\) is asymptotically negative if there exists \(x_0\) such that \(f(x) {\lt} 0\) for all \(x \ge x_0\).

\(f\) is asymptotically negative if there exists \(x_0\) such that \(f(x) \le 0\) for all \(x \ge x_0\).

\(f\) is asymptotically nonpositive if there exists \(x_0\) such that \(f(x) \ge 0\) for all \(x \ge x_0\).

\(f\) is asymptotically positive if there exists \(x_0\) such that \(f(x) {\gt} 0\) for all \(x \ge x_0\).

\(f\) is asymptotically dominated by \(g\) if for all \(k {\gt} 0\) \(f\) is asymptotically less than \(k*g\).

(Big O notation) \(f(x) \in O(g(x))\) if it is asymptotically bounded above by \(g(x)\).

(Big Omega notation) \(f(x) \in \Omega (g(x))\) if it is asymptotically bounded below by \(g(x)\).

Let \(x \in \mathbb {R}\) and \(n \in \mathbb {N}\). A geometric sum is a sum of the form

Let \(T f : \mathbb {N} \rightarrow \mathbb {N}\) be functions such that \(T\) is monotone and the recurrence

holds for all \(n \ge n\_ 0\) for some \(a {\gt} 0\), \(n\_ 0 {\gt} 1\) and \(b {\gt} n\_ 0\). Let also \(f(n) \in \Omega (n^d)\) for some \(d \ge 1\). The above recurrence is a lower master recurrence with parameters \((a, n\_ 0, b, d)\).

(Small O notation) \(f(x) \in o(g(x))\) if it is asymptotically dominated by \(g(x)\).

(Small Omega notation) \(f(x) \in \omega (g(x))\) if it asymptotically dominates \(g(x)\).

(Big Theta notation) \(f(x) \in \Theta (g(x))\) if it is asymptotically bounded by \(g(x)\).

Let \(T f : \mathbb {N} \rightarrow \mathbb {N}\) be functions such that \(T\) is monotone and the recurrence

holds for all \(n \ge n\_ 0\) for some \(a {\gt} 0\), \(n\_ 0 {\gt} 1\) and \(b {\gt} n\_ 0\). Let also \(f(n) \in O(n^d)\) for some \(d \ge 1\). The above recurrence is an upper master recurrence with parameters \((a, n\_ 0, b, d)\).

Let \(f\_ 1\) and \(f\_ 2\) be bounded above by \(g\). Then \(f\_ 1 + f\_ 2\) is also bounded above by \(g\).

Let \(f\_ 1\) be bounded above by \(g\) and let \(f\_ 2\) be asymptotically negative. Then \(f\_ 1 + f\_ 2\) is bounded above by \(g\).

Let \(c {\lt} 0\). If \(f\) is bounded above by \(g\), then \(c \cdot f\) is bounded above by \(-g\).

Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonnegative functions such that \(f\_ 1\) is asymptotically bounded above by \(g\_ 1\) and \(f\_ 2\) is asymptotically bounded above by \(g\_ 2\). Then \(f\_ 1 * f\_ 2\) is asymptotically bounded above by \(g\_ 1 * g\_ 2\).

If \(f\) is dominated by \(g\), then it’s also bounded above by \(g\).

Let \(c {\gt} 0\). If \(f\) is bounded above by \(g\), then \(c \cdot f\) is also bounded above by \(g\).

\(f\) is asymptotically bounded above by itself.

If \(f\) is asymptotically bounded above by \(g\) and \(g\) is asymptotically bounded above by \(h\), then \(f\) is asymptotically bounded above by \(h\).

Let \(f\_ 1\) and \(f\_ 2\) be bounded by \(g\). Then \(f\_ 1 + f\_ 2\) is also bounded by \(g\).

Let \(f\_ 1\) be bounded by \(g\). Let also \(f\_ 2\) be asymptotically negative and bounded below by \(g\). Then \(f\_ 1 + f\_ 2\) is bounded by \(g\).

Let \(f\_ 1\) be bounded by \(g\). Let also \(f\_ 2\) be asymptotically negative and let \(f\_ 2\) dominate \(g\). Then \(f\_ 1 + f\_ 2\) is bounded by \(g\).

Let \(f\_ 1\) be bounded by \(g\). Let also \(f\_ 2\) be asymptotically positive and bounded above by \(g\). Then \(f\_ 1 + f\_ 2\) is bounded by \(g\).

Let \(f\_ 1\) be bounded by \(g\). Let also \(f\_ 2\) be asymptotically positive and let \(f\_ 2\) be dominated by \(g\). Then \(f\_ 1 + f\_ 2\) is bounded by \(g\).

Let \(f\_ 1\) and \(f\_ 2\) be bounded below by \(g\). Then \(f\_ 1 + f\_ 2\) is also bounded below by \(g\).

Let \(f\_ 1\) be bounded below by \(g\) and let \(f\_ 2\) be asymptotically positive. Then \(f\_ 1 + f\_ 2\) is bounded below by \(g\).

Let \(c {\lt} 0\). If \(f\) is bounded below by \(g\), then \(c \cdot f\) is bounded below by \(-g\).

Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonpositive functions such that \(f\_ 1\) is asymptotically bounded below by \(g\_ 1\) and \(f\_ 2\) is asymptotically bounded below by \(g\_ 2\). Then \(f\_ 1 * f\_ 2\) is asymptotically bounded below by \(g\_ 1 * g\_ 2\).

If \(f\) dominates \(g\), then it’s bounded below by \(g\).

Let \(c {\gt} 0\). If \(f\) is bounded below by \(g\), then \(c \cdot f\) is also bounded below by \(g\).

\(f\) is asymptotically bounded below by itself.

If \(f\) is asymptotically bounded below by \(g\) and \(g\) is asymptotically bounded below by \(h\), then \(f\) is asymptotically bounded below by \(h\).

\(f\) is asymptotically bounded above and below by \(g\) if and only if \(f\) is asymptotically bounded by \(g\).

Let \(c {\lt} 0\). If \(f\) is bounded by \(g\), then \(c \cdot f\) is bounded by \(-g\).

Let \(c {\gt} 0\). If \(f\) is bounded by \(g\), then \(c \cdot f\) is also bounded by \(g\).

\(f\) is asymptotically bounded by itself.

If \(f\) is asymptotically bounded by \(g\) and \(g\) is asymptotically bounded by \(h\), then \(f\) is asymptotically bounded by \(h\).

Let \(f\_ 1\) be asymptotically greater than \(g\_ 1\) and \(f\_ 2\) be asymptotically greater than \(g\_ 2\). Then \(f\_ 1 + f\_ 2\) is asymptotically greater than \(g\_ 1 + g\_ 2\).

Let \(f\_ 1\) be asymptotically positive. Let also \(f\_ 2\) be asymptotically greater than \(g\). Then \(f\_ 1 + f\_ 2\) is asymptotically greater than \(g\).

Let \(c {\lt} 0\) and let \(f\) be asymptotically greater than \(g\). Then \(c \cdot f\) is asymptotically less than \(c \cdot g\).

Let \(f\) be asymptotically greater than \(g\). Then \(g\) is asymptotically less than \(f\).

Let \(c {\gt} 0\) and let \(f\) be asymptotically greater than \(g\). Then \(c \cdot f\) is asymptotically greater than \(c \cdot g\).

\(f\) is asymptotically greater than \(f\).

If \(f\) is asymptotically greater than \(g\) and \(g\) is asymptotically greater than \(h\), then \(f\) is asymptotically greater than \(h\).

Let \(f\_ 1\) be asymptotically less than \(g\_ 1\) and \(f\_ 2\) be asymptotically less than \(g\_ 2\). Then \(f\_ 1 + f\_ 2\) is asymptotically less than \(g\_ 1 + g\_ 2\).

Let \(f\_ 1\) be asymptotically negative. Let also \(f\_ 2\) be asymptotically less than \(g\). Then \(f\_ 1 + f\_ 2\) is asymptotically less than \(g\).

Let \(c {\lt} 0\) and let \(f\) be asymptotically less than \(g\). Then \(c \cdot f\) is asymptotically greater than \(c \cdot g\).

Let \(f\) be asymptotically less than \(g\). Then \(g\) is asymptotically greater than \(f\).

Let \(c {\gt} 0\) and let \(f\) be asymptotically less than \(g\). Then \(c \cdot f\) is asymptotically less than \(c \cdot g\).

\(f\) is asymptotically less than \(f\).

If \(f\) is asymptotically less than \(g\) and \(g\) is asymptotically less than \(h\), then \(f\) is asymptotically less than \(h\).

If \(f\) asymptotically dominates \(g\) and \(g\) asymptotically dominates \(h\), then \(f\) asymptotically dominates \(h\).

Let \(f\) be asymptotically less than \(g\) and let \(g\) be asymptotically negative. Then \(f\) is asymptotically negative.

Let \(f\) be asymptotically negative and let it be asymptotically greater than \(g\). Then \(g\) is asymptotically negative.

If \(f\) is asymptotically negative, then \(-f\) is asymptotically positive.

Let \(f\) be asymptotically greater than \(g\) and let \(g\) be asymptotically negative. Then \(g\) is asymptotically negative.

If \(f\) is asymptotically positive, then \(-f\) is asymptotically negative.

Let \(f\) be asymptotically positive and let it be asymptotically less than \(g\). Then \(g\) is asymptotically positive.

If \(f\) is asymptotically dominated by \(g\) and \(g\) is asymptotically dominated by \(h\), then \(f\) is asymptotically dominated by \(h\).

Let \(f\_ 1(x), f\_ 2(x) \in O(g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in O(g(x))\).

Let \(f\_ 1(x) \in O(g(x))\) and let \(f\_ 2\) be asymptotically negative. Then \(f\_ 1(x) + f\_ 2(x) \in O(g(x))\).

Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\). Then \(T(n) \in O(n^{\log _b{a}} + \sum _{k=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^k n^d)\).

Let \(c {\lt} 0\). If \(f(x) \in O(g(x))\), then \(c \cdot f(x) \in O(-g(x))\).

Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonnegative functions such that \(f\_ 1(x) \in O(g\_ 1(x))\) and \(f\_ 2(x) \in O(g\_ 2(x))\). Then \(f\_ 1(x) * f\_ 2(x) \in O(g\_ 1(x) * g\_ 2(x))\).

If \(f(x) \in o(g(x))\), then \(f(x) \in O(f(x))\).

Let \(c {\gt} 0\). If \(f(x) \in O(g(x))\), then \(c \cdot f(x) \in O(g(x))\).

\(f(x) \in O(f(x))\).

If \(f(x) \in O(g(x))\) and \(g(x) \in O(h(x))\), then \(f(x) \in O(h(x))\).

Let \(f\_ 1(x), f\_ 2(x) \in \Omega (g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Omega (g(x))\).

Let \(f\_ 1(x) \in \Omega (g(x))\) and let \(f\_ 2\) be asymptotically positive. Then \(f\_ 1(x) + f\_ 2(x) \in \Omega (g(x))\).

Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\). Then \(T(n) \in \Omega (\sum _{k=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^k n^d)\).

Let \(c {\lt} 0\). If \(f \in \Omega (g(x))\), then \(c \cdot f(x) \in \Omega (-g(x))\).

Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonpositive functions such that \(f\_ 1(x) \in \Omega (g\_ 1(x))\) and \(f\_ 2(x) \in \Omega (g\_ 2(x)\). Then \(f\_ 1(x) * f\_ 2(x) \in \Omega (g\_ 1(x) * g\_ 2(x))\).

Let \(c {\gt} 0\). If \(f(x) \in \Omega (g(x))\), then \(c \cdot f(x) \in \Omega (g(x))\) is also bounded below by \(g\).

Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\). Then \(T(n) \in \Omega (n^d)\).

\(f(x) \in \Omega (f(x))\).

If \(f(x) \in \Omega (g(x))\) and \(g(x) \in \Omega (h(x))\), then \(f(x) \in \Omega (h(x))\).

Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \Omega (g(x))\).

Let \(g\) be asymptotically positive. Then it does not hold that both \(f\) is asymptotically bounded above by \(g\) and \(f\) asymptotically dominate \(g\).

Let \(g\) be asymptotically positive. Then \(f\) is not both asymptotically bounded below by \(g\) and asymptotically dominated by \(g\).

Let \(g\) be asymptotically positive. Then it is not true that both \(f\) is asymptotically dominated by \(g\) and that \(f\) dominates \(g\).

Let \(g\) be asymptotically positive. Then \(f(x) \in o(g(x))\) and \(f(x) \in \omega (g(x))\) are not both true.

Let \(g\) be asymptotically positive. If \(f(x) \in \Omega (g(x))\) then \(f(x) \notin o(g(x))\).

Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \omega (g(x))\).

Let \(g\) be asymptotically positive. If \(f(x) \in \Theta (g(x))\) then \(f(x) \notin o(g(x))\).

Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \omega (g(x))\).

Let \(g\) be asymptotically positive. If \(f(x) \in \Theta (g(x))\) then \(f(x) \notin \omega (g(x))\).

Let \(g\) be asymptotically positive. Then \(f(x) \in \Theta (g(x))\) and \(f(x) \in o(g(x))\) are not both true.

Let \(g\) be asymptotically positive. Then \(f(x) \in \Theta (g(x))\) and \(f(x) \in \omega (g(x))\) are not both true.

Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \Theta (g(x))\).

Let \(g\) be asymptotically positive. If \(f(x) \in \omega (g(x))\) then \(f(x) \notin \Theta (g(x))\).

If \(f(x) \in o(g(x))\) and \(g(x) \in o(h(x))\), then \(f(x) \in o(h(x))\).

If \(f(x) \in \omega (g(x))\) and \(g(x) \in \omega (h(x))\), then \(f(x) \in \omega (h(x))\).

Let \(f\_ 1(x), f\_ 2(x) \in \Theta (g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).

Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically negative and \(f\_ 2(x) \in \Omega (g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).

Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically positive and \(f\_ 2(x) \in O(g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).

Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically positive and \(f\_ 2(x) \in o(g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).

Let \(c {\lt} 0\). If \(f(x) \in \Theta (g(x))\), then \(c \cdot f \in \Theta (-g(x))\).

Let \(c {\gt} 0\). If \(f(x) \in \Theta (g(x))\), then \(c \cdot f(x) \in \Theta (g(x))\).

\(f(x) \in \Theta (f(x))\).

If \(f(x) \in \Theta (g(x))\) and \(g(x) \in \Theta (h(x))\), then \(f(x) \in \Theta (h(x))\).

Let \(0 {\lt} x {\lt} 1\) and \(n \in \mathbb {N}\). Then the following inequality holds:

Let \(x \neq 1\) and \(n \in \mathbb {N}\). Then the following inequality holds:

Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonpositive functions. If f\(\_ 1\) is asymptotically greater than \(g\_ 1\) and \(f\_ 2\) is asymptotically greater than \(g\_ 2\), then \(f\_ 1 * f\_ 2\) is asymptotically less than \(g\_ 1 * g\_ 2\).

\(f\) is asymptotically less than \(g\) if and only if \(g\) is asymptotically greater than \(f\).

Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonnegative functions. If f\(\_ 1\) is asymptotically less than \(g\_ 1\) and \(f\_ 2\) is asymptotically less than \(g\_ 2\), then \(f\_ 1 * f\_ 2\) is asymptotically less than \(g\_ 1 * g\_ 2\).

\(f(x) \in O(g(x))\) and \(f(x) \in \Omega (g(x))\) if and only if \(f(x) \in \Theta (g(x))\).

Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\), where \(a = b^d\). Then \(T(n) \in O(n^d \log _b{n})\).

Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\), where \(a {\gt} b^d\). Then \(T(n) \in O(n^{\log _b{a}})\).

Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\), where \(a {\lt} b^d\). Then \(T(n) \in O(n^d)\).

Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a = b^d\). Then \(T(n) \in \Omega (n^d \log _b{n})\).

Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a {\gt} b^d\). Then \(T(n) \in \Omega (n^{\log _b{a}})\).

If \(f(x) \in \omega (g(x))\), then \(f(x) \in \Omega (g(x))\).

Let \(f\) be asymptotically positive. If \(f\) is asymptotically bounded above by \(g\), then \(f\) does not asymptotically dominate \(g\).

Let \(f\) be asymptotically positive. If \(f\) is bounded below by \(g\), then \(f\) does not dominate \(g\).

Let \(f\) be asymptotically positive. If \(f\) is asymptotically bounded below by \(g\), then \(f\) is not asymptotically dominated by \(g\).

Let \(g\) be asymptotically positive. If \(f\) is asymptotically dominated by \(g\), then \(f\) does not asymptotically dominate \(g\).

Let \(f\) be asymptotically positive. If \(f\) is asymptotically bounded below by \(g\), then \(f\) is not asymptotically dominated by \(g\).

Let \(g\) be asymptotically positive. If \(f\) asymptotically dominates \(g\), then \(f\) is not asymptotically dominated by \(g\).

Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically negative and \(f\_ 2(x) \in \omega (g(x))\). Then \(f\_ 1(X) + f\_ 2(x) \in \Theta (g(x))\).

Let \(T\) and \(f\) form an upper and lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a = b^d\). Then \(T(n) \in \Theta (n^d \log _b{a})\).

Let \(T\) and \(f\) form an upper and lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a {\gt} b^d\). Then \(T(n) \in \Theta (n^{\log _b{n}})\).

Let \(T\) and \(f\) form an upper and lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a {\lt} b^d\). Then \(T(n) \in \Theta (n^d)\).