TADM2E 2.8 - Revision history

Matt: Undo revision 854 by Tada! (talk)

2020-07-23T15:54:34Z

Undo revision 854 by Tada! (talk)

Tada!: Blanked the page

2020-07-20T23:35:32Z

Blanked the page

Jeelshah: /* f(n)=2^n; g(n)=10n^2 */

2016-06-27T20:41:44Z

‎f(n)=2^n; g(n)=10n^2

Algowikiadmin: Recovering wiki

2014-09-11T18:23:51Z

Recovering wiki

Show changes

Algowikiadmin: Recovering wiki

2014-09-11T18:14:08Z

Recovering wiki

New page

=2-8.=

For each of the following pairs of functions, either <math>f(n)</math> is in <math>O(g(n))</math>, <math>f(n)</math> is in <math>\Omega(g(n))</math>, or <math>f(n)=\Theta(g(n))</math>. Determine which relationship is correct and briefly explain why.

==<math>f(n)=\log n^2</math>; <math>g(n)=\log n</math> + <math>5</math>==
Answer: <math>\log n^2 = \Theta (\log n + 5)</math>

Solution:

<math>\log n^2 = 2 \times \log n</math>

<math>2 \times \log n \le 2 \times \log n + 10</math>

<math>\log n^2 \le 2 (\log n + 5)</math>

<math>\log n^2 \le C (\log n + 5)</math> (where <math>C=2</math>)

<math>\log n^2 = O (\log n + 5)</math>

Also:

<math>\log n + 5 \le \log n + 5 \log n</math>

<math>\log n + 5 \le 6 \log n</math>

<math>\log n + 5 \le 3 \times 2 \log n</math>

<math>3 \times \log n^2 \ge \log n + 5 </math>

<math>\log n^2 \ge C \times (\log n + 5)</math> (Where <math>C =\frac{1}{3}</math>)

<math>log n^2 = \Omega (\log n + 5)</math>

And therefore:

<math>log n^2 = \Theta (\log n + 5)</math>

==<math>f(n)=\sqrt{n}</math>; <math>g(n)=\log(n^2)</math>==

Answer: <math>f(n) = \Omega(g(n))</math>

Solution:

<math>g(n) = \log (n^2) = 2 * \log (n)</math>

<math>\lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty</math>

==<math>f(n)=\log^2(n)</math>; <math>g(n)=\log (n)</math>==

Answer: <math>f(n) = \Omega(g(n))</math>

Solution:

<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>

==<math>f(n)=n</math>; <math>g(n)=\log^2(n)</math>==

Answer: <math>f(n) = \Omega(g(n))</math>

Solution:

<math>\lim_{n \to \infty} \frac{n}{\log^2(n)} = \lim_{n \to \infty} ((\frac{\sqrt{n}}{\log(n)})^2) = (\lim_{n \to \infty} \frac{\sqrt{n}}{\log(n)})^2 = \infty</math>

==<math>f(n)=n * \log(n) + n</math>; <math>g(n)=\log (n)</math>==

Answer: <math>f(n) = \Omega(g(n))</math>

Solution:

<math>\lim_{n \to \infty} \frac{n * \log(n) + n}{log(n)} = \lim_{n \to \infty} (\frac{n * \log(n)}{log(n)} + \frac{n}{log(n)}) = \lim_{n \to \infty} (n + \frac{n}{log(n)}) = \infty</math>

==<math>f(n)=10</math>; <math>g(n)=\log (10)</math>==

Answer: <math>f(n) = \Theta(g(n))</math>

Solution: Both are constants. Constants are always within a constant factor, <math>c</math>, of each other (as <math>n \rightarrow \infty</math>).

==<math>f(n)=2^n</math>; <math>g(n)=10n^2</math>==

Answer: <math>f(n) = \Omega(g(n))</math>

Solution:

<math>\lim_{n \to \infty} \frac{2^n}{10n^2} = \frac{1}{10} (\lim_{n \to \infty} \frac{2^n}{n^2}) = \frac{1}{10} (\lim_{n \to \infty} \frac{n * 2^{n-1}}{2 * n})</math> <span style='padding-left:10px'>(L'Hopital's Rule)</span>

<math> = \frac{1}{10} (\lim_{n \to \infty} 2^{n-2}) = \infty </math>

==<math>f(n)=2^n</math>; <math>g(n)=3^n</math>==

Answer: <math>f(n) = O(g(n))</math>

Solution:

<math>\lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0</math>

← Older revision		Revision as of 23:35, 20 July 2020
Line 1:		Line 1:
−	~~=2-8.=~~

−	For each of the following pairs of functions, either <math>f(n)</math> is in <math>O(g(n))</math>, <math>f(n)</math> is in <math>\Omega(g(n))</math>, or <math>f(n)=\Theta(g(n))</math>. Determine which relationship is correct and briefly explain why.
−
−
−	~~==<math>f(n)=\log n^2</math>; <math>g(n)=\log n</math> + <math>5</math>==~~
−	~~Answer: <math>\log n^2 = \Theta (\log n + 5)</math>~~
−
−
−	~~Solution:~~
−
−	~~<math>\log n^2 = 2 \times \log n</math>~~
−
−	~~<math>2 \times \log n \le 2 \times \log n + 10</math>~~
−
−	~~<math>\log n^2 \le 2 (\log n + 5)</math>~~
−
−	~~<math>\log n^2 \le C (\log n + 5)</math> (where <math>C=2</math>)~~
−
−	~~<math>\log n^2 = O (\log n + 5)</math>~~
−
−	~~Also:~~
−
−	~~<math>\log n + 5 \le \log n + 5 \log n</math>~~
−
−	~~<math>\log n + 5 \le 6 \log n</math>~~
−
−	~~<math>\log n + 5 \le 3 \times 2 \log n</math>~~
−
−	~~<math>3 \times \log n^2 \ge \log n + 5 </math>~~
−
−	~~<math>\log n^2 \ge C \times (\log n + 5)</math> (Where <math>C =\frac{1}{3}</math>)~~
−
−	~~<math>log n^2 = \Omega (\log n + 5)</math>~~
−
−	~~And therefore:~~
−
−	~~<math>log n^2 = \Theta (\log n + 5)</math>~~
−
−
−	~~==<math>f(n)=\sqrt{n}</math>; <math>g(n)=\log(n^2)</math>==~~
−
−	~~Answer: <math>f(n) = \Omega(g(n))</math>~~
−
−
−	~~Solution:~~
−
−	~~<math>g(n) = \log (n^2) = 2 * \log (n)</math>~~
−
−	~~<math>\lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty</math>~~
−
−
−	~~==<math>f(n)=\log^2(n)</math>; <math>g(n)=\log (n)</math>==~~
−
−	~~Answer: <math>f(n) = \Omega(g(n))</math>~~
−
−
−	~~Solution:~~
−
−	~~<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>~~
−
−
−	~~==<math>f(n)=n</math>; <math>g(n)=\log^2(n)</math>==~~
−
−	~~Answer: <math>f(n) = \Omega(g(n))</math>~~
−
−
−	~~Solution:~~
−
−	~~<math>\lim_{n \to \infty} \frac{n}{\log^2(n)} = \lim_{n \to \infty} ((\frac{\sqrt{n}}{\log(n)})^2) = (\lim_{n \to \infty} \frac{\sqrt{n}}{\log(n)})^2 = \infty</math>~~
−
−
−	~~==<math>f(n)=n * \log(n) + n</math>; <math>g(n)=\log (n)</math>==~~
−
−	~~Answer: <math>f(n) = \Omega(g(n))</math>~~
−
−
−	~~Solution:~~
−
−	~~<math>\lim_{n \to \infty} \frac{n * \log(n) + n}{log(n)} = \lim_{n \to \infty} (\frac{n * \log(n)}{log(n)} + \frac{n}{log(n)}) = \lim_{n \to \infty} (n + \frac{n}{log(n)}) = \infty</math>~~
−
−
−	~~==<math>f(n)=10</math>; <math>g(n)=\log (10)</math>==~~
−
−	~~Answer: <math>f(n) = \Theta(g(n))</math>~~
−
−
−	~~Solution: Both are constants. Constants are always within a constant factor, <math>c</math>, of each other (as <math>n \rightarrow \infty</math>).~~
−
−
−	~~==<math>f(n)=2^n</math>; <math>g(n)=10n^2</math>==~~
−
−	~~Answer: <math>f(n) = \Omega(g(n))</math>~~
−
−
−	~~Solution:~~
−
−	~~<math>~~
−	~~\begin{align}~~
−	~~&\lim_{n \to \infty} \frac{2^n}{10n^2} \\~~
−	~~&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2^n}{n^2}\right) \\~~
−	~~&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{\ln(2)\cdot 2^n}{2 \cdot n}\right) \text{L'Hopital's Rule} \\~~
−	~~&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2\ln(2)\cdot 2^n}{2}\right) \text{L'Hopital's Rule} \\~~
−	~~&\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n \\~~
−	~~&\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n = \infty~~
−	~~\end{align}~~
−	~~</math>~~
−
−	~~==<math>f(n)=2^n</math>; <math>g(n)=3^n</math>==~~
−
−	~~Answer: <math>f(n) = O(g(n))</math>~~
−
−
−	~~Solution:~~
−
−	~~<math>\lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0</math>~~

@@ Line 96: / Line 96: @@
 Solution:
-<math>\lim_{n \to \infty} \frac{2^n}{10n^2} = \frac{1}{10} (\lim_{n \to \infty} \frac{2^n}{n^2}) = \frac{1}{10} (\lim_{n \to \infty} \frac{n * 2^{n-1}}{2 * n})</math> <span style='padding-left:10px'>(L'Hopital's Rule)</span>
+<math>
+\begin{align}
-<math> = \frac{1}{10} (\lim_{n \to \infty} 2^{n-2}) = \infty </math>
+&\lim_{n \to \infty} \frac{2^n}{10n^2} \\
+&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2^n}{n^2}\right) \\
+&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{\ln(2)\cdot 2^n}{2 \cdot n}\right) \text{L'Hopital's Rule} \\
 ==<math>f(n)=2^n</math>; <math>g(n)=3^n</math>==

← Older revision	Revision as of 15:54, 23 July 2020
Line 1:	Line 1:
	+	=2-8.=

	+	For each of the following pairs of functions, either <math>f(n)</math> is in <math>O(g(n))</math>, <math>f(n)</math> is in <math>\Omega(g(n))</math>, or <math>f(n)=\Theta(g(n))</math>. Determine which relationship is correct and briefly explain why.
	+
	+
	+	==<math>f(n)=\log n^2</math>; <math>g(n)=\log n</math> + <math>5</math>==
	+	Answer: <math>\log n^2 = \Theta (\log n + 5)</math>
	+
	+
	+	Solution:
	+
	+	<math>\log n^2 = 2 \times \log n</math>
	+
	+	<math>2 \times \log n \le 2 \times \log n + 10</math>
	+
	+	<math>\log n^2 \le 2 (\log n + 5)</math>
	+
	+	<math>\log n^2 \le C (\log n + 5)</math> (where <math>C=2</math>)
	+
	+	<math>\log n^2 = O (\log n + 5)</math>
	+
	+	Also:
	+
	+	<math>\log n + 5 \le \log n + 5 \log n</math>
	+
	+	<math>\log n + 5 \le 6 \log n</math>
	+
	+	<math>\log n + 5 \le 3 \times 2 \log n</math>
	+
	+	<math>3 \times \log n^2 \ge \log n + 5 </math>
	+
	+	<math>\log n^2 \ge C \times (\log n + 5)</math> (Where <math>C =\frac{1}{3}</math>)
	+
	+	<math>log n^2 = \Omega (\log n + 5)</math>
	+
	+	And therefore:
	+
	+	<math>log n^2 = \Theta (\log n + 5)</math>
	+
	+
	+	==<math>f(n)=\sqrt{n}</math>; <math>g(n)=\log(n^2)</math>==
	+
	+	Answer: <math>f(n) = \Omega(g(n))</math>
	+
	+
	+	Solution:
	+
	+	<math>g(n) = \log (n^2) = 2 * \log (n)</math>
	+
	+	<math>\lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty</math>
	+
	+
	+	==<math>f(n)=\log^2(n)</math>; <math>g(n)=\log (n)</math>==
	+
	+	Answer: <math>f(n) = \Omega(g(n))</math>
	+
	+
	+	Solution:
	+
	+	<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>
	+
	+
	+	==<math>f(n)=n</math>; <math>g(n)=\log^2(n)</math>==
	+
	+	Answer: <math>f(n) = \Omega(g(n))</math>
	+
	+
	+	Solution:
	+
	+	<math>\lim_{n \to \infty} \frac{n}{\log^2(n)} = \lim_{n \to \infty} ((\frac{\sqrt{n}}{\log(n)})^2) = (\lim_{n \to \infty} \frac{\sqrt{n}}{\log(n)})^2 = \infty</math>
	+
	+
	+	==<math>f(n)=n * \log(n) + n</math>; <math>g(n)=\log (n)</math>==
	+
	+	Answer: <math>f(n) = \Omega(g(n))</math>
	+
	+
	+	Solution:
	+
	+	<math>\lim_{n \to \infty} \frac{n * \log(n) + n}{log(n)} = \lim_{n \to \infty} (\frac{n * \log(n)}{log(n)} + \frac{n}{log(n)}) = \lim_{n \to \infty} (n + \frac{n}{log(n)}) = \infty</math>
	+
	+
	+	==<math>f(n)=10</math>; <math>g(n)=\log (10)</math>==
	+
	+	Answer: <math>f(n) = \Theta(g(n))</math>
	+
	+
	+	Solution: Both are constants. Constants are always within a constant factor, <math>c</math>, of each other (as <math>n \rightarrow \infty</math>).
	+
	+
	+	==<math>f(n)=2^n</math>; <math>g(n)=10n^2</math>==
	+
	+	Answer: <math>f(n) = \Omega(g(n))</math>
	+
	+
	+	Solution:
	+
	+	<math>
	+	\begin{align}
	+	&\lim_{n \to \infty} \frac{2^n}{10n^2} \\
	+	&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2^n}{n^2}\right) \\
	+	&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{\ln(2)\cdot 2^n}{2 \cdot n}\right) \text{L'Hopital's Rule} \\
	+	&\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2\ln(2)\cdot 2^n}{2}\right) \text{L'Hopital's Rule} \\
	+	&\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n \\
	+	&\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n = \infty
	+	\end{align}
	+	</math>
	+
	+	==<math>f(n)=2^n</math>; <math>g(n)=3^n</math>==
	+
	+	Answer: <math>f(n) = O(g(n))</math>
	+
	+
	+	Solution:
	+
	+	<math>\lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0</math>