> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-i-foundations/3.-characterizing-running-times.md). # 3. Characterizing Running Times ## Exercises ### 3.1-1 **Available in the latest revision of the IM.** ### 3.1-2 **Available in the latest revision of the IM.** ### 3.1-3 **Available in the latest revision of the IM.** ### 3.2-1 🌟 {% hint style="success" %} Proves that $$\max{f(n), g(n)}=\Theta(f(n)+g(n))$$. {% endhint %} **Available in the latest revision of the IM.** ### 3.2-2 **Available in the latest revision of the IM.** ### 3.2-3 **Available in the latest revision of the IM.** ### 3.2-4 **Available in the latest revision of the IM.** ### 3.2-5 **Available in the latest revision of the IM.** ### 3.2-6 **Available in the latest revision of the IM.** ### 3.2-7 🌟 {% hint style="success" %} Defines asymptotic tight bounds for a function $$f(n,m)$$ with two independent arguments. {% endhint %} **Available in the latest revision of the IM.** ### 3.3-1 🌟 {% hint style="success" %} Proves some properties about monotonically increasing functions $$f(n)$$ and $$g(n)$$. {% endhint %} Let $$m \le n$$. This implies that $$f(m) \le f(n)$$ and $$g(m) \le g(n)$$, since they are monotonically increasing functions. If we add up these inequalities, then we get $$f(m)+g(m)\le f(n)+g(n)$$, thus proving that $$f(n)+g(n)$$ is monotonically increasing. If we multiply these inequalities, provided that both $$f$$ and $$g$$ are nonnegative, then we get $$f(m) \cdot g(m)\le f(n) \cdot g(n)$$, thus proving that $$f(n) \cdot g(n)$$ is monotonically increasing. By definition $$f(g(m)) \le f(g(n))$$, so the composition $$f(g(n))$$ is also monotonically increasing. ### 3.3-2 🌟 {% hint style="success" %} Proves that $$\lfloor \alpha n\rfloor+\lceil(1-\alpha)n\rceil=n$$ for any integer $$n$$ and real $$0 \le \alpha \le 1$$. {% endhint %} **Available in the latest revision of the IM.** ### 3.3-3 🌟 {% hint style="success" %} Proves that $$(n+o(n))^k=\Theta(n^k)$$ for any real constant $$k$$, thus $$\lceil n\rceil^k=\Theta(n^k)$$ and $$\lfloor n\rfloor^k=\Theta(n^k)$$. {% endhint %} $$f(n)=o(n)$$ implies that $$0 \le f(n) < cn$$ for all $$c >0$$ and $$n \ge n\_0$$. For $$n \ge n\_0$$ we have$$n \le n + f(n) < (1+c)n$$, thus $$n+o(n)=\Theta(n)$$, since we can choose any constant greater than 1 for the upper bound. Analogously, we can prove that $$n-o(n)=\Theta(n)$$ by simply reversing inequalities $$n \ge n-f(n)>(1-c)n$$ and choosing any positive constant less than 1 for the lower bound. Consequently, $$ \underbrace{(n+o(n))^k}\_{f(n)}=(\Theta(n))^k \implies c\_1^kn^k \le f(n) \le c\_2^kn^k \implies f(n)=\Theta(n^k), $$ for any real constant $$k$$. As a side note, if $$k <0$$, then the inequalities of $$\Theta$$ are reverse of those when $$k>0$$. By definition, $$n \le \lceil n \rceil < n + 1$$. Let $$f(n) = \lceil n \rceil - n$$. Since $$0 \le f(n) < 1 \implies f(n)=o(n)$$ (any constant is asymptotically smaller than $$n$$), this gives $$\lceil n\rceil=n+o(n)$$, thus $$\lceil n\rceil^k=\Theta(n^k)$$. In virtually the same way, we can show that $$\lfloor n\rfloor=n-o(n)$$, so $$\lfloor n\rfloor^k=\Theta(n^k)$$. ### 3.3-4 #### a. $$ \begin{align\*} \large a^{\large\log\_b c} &= \large a^{\cfrac {\log\_a c}{\log\_a b}} && \text{(by equation (3.19))} \\ &= \large c^{\cfrac {1}{\log\_a b}} && \text{(by equation (3.17))} \\ &= \large c^{\large\log\_b a}. \end{align\*} $$ #### b. $$ \frac {n!}{n^n}=\frac{1}{n} \cdot \frac{2}{n} \dots \frac{n}{n} \implies \lim\_{n \to \infin} \frac{n!}{n^n}=0. $$ Observe that the largest term on the right side is 1, whilst the initial terms tend to zero as n increases. Therefore, $$n!=o(n^n)$$. $$ \frac {n!}{2^n}=\frac{1}{2} \cdot \frac{2}{2} \dots \frac{n}{2} \implies \lim\_{n \to \infin} \frac{n!}{2^n}=\infin. $$ Here, we have an opposite situation, thus $$n!=\omega(2^n)$$. A weak upper bound on the factorial function is $$n! \le n^n$$, so $$\lg n! \le n\lg n=O(n\lg n)$$. $$ \begin{align\*} \lg n! &= \lg {(\sqrt{2\pi n},(n/e)^n e^{\alpha\_n})} && \text{(by equation (3.29))} \\ &> \lg {(n/e)^n} \\ &> \lg {(\sqrt n)^n} && \text{(} e < \sqrt n \text{ when } n \ge 9 \text{)} \\ &= \frac {n \lg n}{2} \\ &\therefore \lg n! = \Omega(n \lg n). \end{align\*} $$ Theorem 3.1 implies that $$\lg n!=\Theta(n\lg n)$$. #### c. Let $$f(n)=\Theta(n)$$. By definition $$c\_1n \le f(n) \le c\_2n$$ for some positive constants and $$n \ge n\_0$$. $$ \begin{align\*} \lg f(n) &\ge \lg c\_1n \\ &=\lg c\_1 + \lg n \\ &\ge \lg \frac{1}{\sqrt n} + \lg n && \text{(when } n \ge 1/c\_1^2 \text{)} \\ &= \lg \sqrt n \\ &= \frac {\lg n}{2} \\ &\therefore \lg f(n) = \Omega(\lg n). \\ \hline \\ \lg f(n) &\le \lg c\_2n \\ &=\lg c\_2 + \lg n \\ &\le 2\lg n && \text{(when } n \ge c\_2 \text{)} \\ &\therefore \lg f(n) = O(\lg n). \end{align\*} $$ Theorem 3.1 implies that $$\lg f(n)=\lg \Theta(n)=\Theta(\lg n)$$ for all $$n \ge \max{n\_0,1/c\_1^2,c\_2}$$. ### ★ 3.3-5 🌟 {% hint style="success" %} Proves that a function $$f(n)$$ is polynomially bounded if and only if $$\lg f(n)= O(\lg n)$$. {% endhint %} **Available in the latest revision of the IM.** ### ★ 3.3-6 **Available in the latest revision of the IM.** ### 3.3-7 **Available in the latest revision of the IM.** ### 3.3-8 **Available in the latest revision of the IM.** ### 3.3-9 🌟 {% hint style="success" %} Illustrates the symmetry property of the $$\Theta$$ notation by showing that $$k\lg k=\Theta(n)$$ implies $$k=\Theta(n/\lg n)$$. {% endhint %} **Available in the latest revision of the IM.** ## Problems ### 3-1 Asymptotic behavior of polynomials In all subproblems, we rely on the fact (stated in the book on page 65) that for an asymptotically positive polynomial $$p(n)$$ of degree $$d$$, we have $$p(n)=\Theta(n^d)$$. Consequently, for some positive constants it holds that $$0 < c\_1n^d \le p(n) \le c\_2n^d$$ for all $$n \ge n\_0$$. #### a. $$n^k \ge n^d$$ for all $$n \ge 1$$, so $$0 < p(n) \le c\_2n^d \le c\_2n^k$$ for all $$n \ge n\_0$$. Thus, $$p(n)=O(n^k)$$. #### b. $$n^k \le n^d$$ for all $$n \ge 1$$, so $$0 < c\_1n^k \le c\_1n^d \le p(n)$$ for all $$n \ge n\_0$$. Thus, $$p(n)=\Omega(n^k)$$. #### c. $$k=d$$ means that $$k \ge d \land k \le d$$, so parts (a) and (b) apply. Theorem 3.1 implies that $$p(n)=\Theta(n^k)$$. #### d. We fix a positive constant $$c$$ and show that for sufficiently large $$n$$ we have $$c\_2n^d < cn^k$$. We can rewrite this inequality as $$c\_2/c < n^{k-d}$$. Apparently, it holds for all $$n > (c\_2/c)^{1/(k-d)}$$. Choosing $$n$$ to be the maximum of this value and $$n\_0$$ ensures that $$0 < p(n)\le c\_2n^d\ cn^k$$. We can rewrite this inequality as $$c/c\_1 < n^{d-k}$$. Apparently, it holds for all $$n > (c/c\_1)^{1/(d-k)}$$. Choosing $$n$$ to be the maximum of this value and $$n\_0$$ ensures that $$0 < cn^k < c\_1n^d \le p(n)$$. As the choice of $$c$$ was arbitrary, the derivation applies to all positive constants, hence $$p(n)=\omega(n^k)$$. ### 3-2 Relative asymptotic growths **Available in the latest revision of the IM.** ### 3-3 Ordering by asymptotic growth rates **Available in the latest revision of the IM.** ### 3-4 Asymptotic notation properties **Available in the latest revision of the IM.** ### 3-5 Manipulating asymptotic notation Assume that all constants introduced in the subproblems are positive. #### a. Let $$g(n)=\Theta(f(n))$$, thus $$0 \le c\_1f(n) \le g(n) \le c\_2f(n)$$ for all $$n \ge n\_g$$. Let $$h(n)=\Theta(g(n))$$, so $$0 \le d\_1g(n) \le h(n) \le d\_2g(n)$$ for all $$n \ge n\_h$$. Substituting $$g(n)$$ with $$f(n)$$ we get $$0 \le d\_1c\_1f(n) \le h(n) \le d\_2c\_2f(n)$$ for all $$n \ge \max{n\_g,n\_h}$$. Therefore, $$h(n)=\Theta(f(n))$$, which concludes the proof. #### b. Let $$g(n)=\Theta(f(n))$$, thus $$0 \le c\_1f(n) \le g(n) \le c\_2f(n)$$ for all $$n \ge n\_g$$. Let $$h(n)=O(f(n))$$, so $$0 \le h(n) \le df(n)$$ for all $$n \ge n\_h$$. By combining these inequalities we get for all $$n \ge \max{n\_g,n\_h}$$ $$ 0 \le c\_1f(n) \le g(n)+h(n) \le (c\_2+d)f(n). $$ Therefore, $$g(n)+h(n)=\Theta(f(n))$$, which concludes the proof. #### c. Let $$h(n)=\Theta(f(n))$$, thus $$0 \le c\_1f(n) \le h(n) \le c\_2f(n)$$ for all $$n \ge n\_h$$. Let $$q(n)=\Theta(g(n))$$, so $$0 \le d\_1g(n) \le q(n) \le d\_2g(n)$$ for all $$n \ge n\_q$$. Adding together these inequalities we get for all $$n \ge \max{n\_h,n\_q}$$ $$ 0 \le \min{c\_1,d\_1}(f(n) +g(n))\le h(n) +q(n)\le \max{c\_2,d\_2}(f(n) +g(n)). $$ Therefore, $$h(n)+q(n)=\Theta(f(n)+g(n))$$, which concludes the proof. #### d. Let $$h(n)=\Theta(f(n))$$, thus $$0 \le c\_1f(n) \le h(n) \le c\_2f(n)$$ for all $$n \ge n\_h$$. Let $$q(n)=\Theta(g(n))$$, so $$0 \le d\_1g(n) \le q(n) \le d\_2g(n)$$ for all $$n \ge n\_q$$. Multiplying together these inequalities we get for all $$n \ge \max{n\_h,n\_q}$$ $$ 0 \le c\_1d\_1(f(n) \cdot g(n)) \le h(n) \cdot q(n) \le c\_2d\_2(f(n) \cdot g(n)). $$ Therefore, $$h(n) \cdot q(n)=\Theta(f(n) \cdot g(n))$$, which concludes the proof. #### e. $$ \begin{align\*} (a\_1n)^{k\_1} \lg^{k\_2} (a\_2n) &= a\_1^{k\_1}n^{k\_1} (\lg n + \lg a\_2)^{k\_2} \\ &= \Theta(a\_1^{k\_1}n^{k\_1}) (\lg n + o(\lg n))^{k\_2} && \text{(by reflexivity)} \\ &= \Theta(n^{k\_1}) \cdot \Theta(\lg n)^{k\_2} && \text{(by Problem 3-4 part (h))} \\ &= \Theta(n^{k\_1}) \cdot \Theta(\lg^{k\_2} n) && \text{(by repeatedly applying part (d))} \\ &= \Theta(n^{k\_1}\lg^{k\_2} n) && \text{(by part (d))}. \end{align\*} $$ ### 3-6 Variations on O and Ω #### a. If $$f(n)=O(g(n))$$ or $$f(n)=\Omega(g(n))$$ (or both), then we are done. Observe that $$f(n)=\Omega(g(n))$$ implies $$f(n)=\overset{\infty}{\Omega}(g(n)).$$ Suppose that $$g(n)$$ cannot bound $$f(n)$$. There must be infinitely many points where $$f(n) > cg(n)$$, otherwise we could find a positive threshold $$n\_0$$ such that $$f(n) \le cg(n)$$ for all $$n \ge n\_0$$. In other words, for any $$n\_0$$ there is some $$m>n\_0$$ where $$f(m) >cg(m)$$. Consequently, $$f(n)=\overset{\infty}{\Omega}(g(n)).$$ #### b. See [Problem 3-2](#id-3-2-relative-asymptotic-growths) row (c). #### c. As shown in part (a), one advantage of using omega infinity over standard omega is that all asymptotically nonnegative functions become asymptotically comparable. On the other hand, omega infinity cannot tell whether one function is "larger" than the other. Oscillations are permitted. Furthermore, we don't know anything about how those infinitely many points are distributed. With omega notation it is clear that the condition holds for all $$n \ge n\_0$$. Finally, omega infinity is unknown to most software engineers. #### d. $$f(n)=\Omega(g(n))$$ implies that $$f(n)$$ is an asymptotically nonnegative function, hence $$f(n)=|f(n)|$$. Consequently, $$f(n)=O'(g(n))$$ is equivalent to $$f(n)=O(g(n))$$, so Theorem 3.1 remains valid. #### e. $$ \begin{align\*} \widetilde{\Omega}(g(n)) = {f(n):,{} & \text{there exist positive constants $c$, $k$, and $n\_0$ such that} \\ & \text{$0 \le \dfrac{cg(n)}{\lg^kn} \le f(n)$ for all $n \ge n\_0$}} \\\[2mm] \widetilde{\Theta}(g(n)) = {f(n):,{} & \text{there exist positive constants $c\_1$, $c\_2$, $k\_1$, $k\_2$, and $n\_0$ such that} \\ & \text{$0 \le \dfrac{c\_1g(n)}{\lg^{k\_1}n} \le f(n) \le c\_2g(n)\lg^{k\_2}n$ for all $n \ge n\_0$}} \end{align\*} $$ The proof of the corresponding analog to Theorem 3.1 is essentially the same as for the original version (see [Exercise 3.2-4](#id-3.2-4)). The only difference is that we should use these new definitions. ### 3-7 Iterated functions **Available in the latest revision of the IM.** --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://evarga.gitbook.io/sh-intro-to-algs/part-i-foundations/3.-characterizing-running-times.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.