TADM2E 2.9 - Revision history

Matt: Undo revision 1147 by FuckyouMatt (talk)

2020-08-02T12:09:22Z

Undo revision 1147 by FuckyouMatt (talk)

FuckyouMatt: Replaced content with "Fuck you matt,"

2020-08-02T03:48:42Z

Replaced content with "Fuck you matt,"

Matt: Undo revision 1065 by FuckMatt (talk)

2020-08-01T01:00:35Z

Undo revision 1065 by FuckMatt (talk)

FuckMatt: Blanked the page

2020-07-31T09:38:17Z

Blanked the page

Algowikiadmin: Recovering wiki

2014-09-11T18:23:53Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:09Z

Recovering wiki

New page

=2-9.=

For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>, determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both.

=='''1.''' <math>f(n) = \frac{n^2 - n}{2}</math>; <math>g(n) = 6 n</math>==

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

Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. <math>n^2</math> outgrows <math>n</math> as <math>n \rightarrow \infty</math>. Therefore, <math>f(n)</math> outgrows <math>g(n)</math>.

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

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

Solution: <math>n^2</math> outgrows n. We ignore <math>2\sqrt{n}</math> since <math>n</math> outgrows <math>\sqrt{n}</math>.

=='''3.''' <math>f(n) = n * log (n) </math>; <math>g(n) = \frac{n \sqrt{n}}{2}</math>==

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

Solution: Both sides have a factor of <math>n</math>, so we ignore it. <math>\sqrt{n}</math> outgrows <math>log(n)</math>, so <math>g(n)</math> is bigger.

=='''4.''' <math>f(n) = n + log(n)</math>; <math>g(n) = \sqrt{n}</math>==

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

Solution: <math>n</math> outgrows <math>\sqrt{n}</math>.

=='''5.''' <math>f(n) = 2 * log^2(n)</math>; <math>g(n) = log(n) + 1</math>==

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

Solution: <math>log^2(n)</math> grows faster than <math>log(n)</math>.

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

=='''6.''' <math>f(n) = 4n * log(n) + n</math>; <math>g(n) = \frac{n^2 - n}{2}</math>==

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

Solution: <math>n^2</math> outgrows <math>n * log(n)</math>.

← Older revision		Revision as of 03:48, 2 August 2020
Line 1:		Line 1:
−	~~=2-9.=~~	+	Fuck you matt,
−
−	~~For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>~~, ~~determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both.~~
−
−	~~=='''1.''' <math>f(n) = \frac{n^2 - n}{2}</math>; <math>g(n) = 6 n</math>==~~
−
−	~~Answer: <math>g(n) = O(f(n)) </math>~~
−
−
−	Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. <math>n^2</math> outgrows <math>n</math> as <math>n \rightarrow \infty</math>. Therefore, <math>f(n)</math> outgrows <math>g(n)</math>.
−
−
−	~~=='''2.''' <math>f(n) = n + 2\sqrt{n}</math>; <math>g(n) = n^2</math>==~~
−
−	~~Answer: <math>f(n) = O(g(n))</math>~~
−
−
−	~~Solution: <math>n^2</math> outgrows n. We ignore <math>2\sqrt{n}</math> since <math>n</math> outgrows <math>\sqrt{n}</math>.~~
−
−
−	~~=='''3.''' <math>f(n) = n * log (n) </math>; <math>g(n) = \frac{n \sqrt{n}}{2}</math>==~~
−
−	~~Answer: <math>f(n) = O(g(n))</math>~~
−
−
−	~~Solution: Both sides have a factor of <math>n</math>, so we ignore it. <math>\sqrt{n}</math> outgrows <math>log(n)</math>, so <math>g(n)</math> is bigger.~~
−
−
−	~~=='''4.''' <math>f(n) = n + log(n)</math>; <math>g(n) = \sqrt{n}</math>==~~
−
−	~~Answer: <math>g(n) = O(f(n))</math>~~
−
−
−	~~Solution: <math>n</math> outgrows <math>\sqrt{n}</math>.~~
−
−
−	~~=='''5.''' <math>f(n) = 2 * log^2(n)</math>; <math>g(n) = log(n) + 1</math>==~~
−
−	~~Answer: <math>g(n) = O(f(n))</math>~~
−
−
−	~~Solution: <math>log^2(n)</math> grows faster than <math>log(n)</math>.~~
−
−	~~<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>~~
−
−
−	~~=='''6.''' <math>f(n) = 4n * log(n) + n</math>; <math>g(n) = \frac{n^2 - n}{2}</math>==~~
−
−	~~Answer: <math>f(n) = O(g(n))</math>~~
−
−
−	~~Solution: <math>n^2</math> outgrows <math>n * log(n)</math>.~~

← Older revision		Revision as of 09:38, 31 July 2020
Line 1:		Line 1:
−	~~=2-9.=~~

−	~~For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>, determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both.~~
−
−	~~=='''1.''' <math>f(n) = \frac{n^2 - n}{2}</math>; <math>g(n) = 6 n</math>==~~
−
−	~~Answer: <math>g(n) = O(f(n)) </math>~~
−
−
−	Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. <math>n^2</math> outgrows <math>n</math> as <math>n \rightarrow \infty</math>. Therefore, <math>f(n)</math> outgrows <math>g(n)</math>.
−
−
−	~~=='''2.''' <math>f(n) = n + 2\sqrt{n}</math>; <math>g(n) = n^2</math>==~~
−
−	~~Answer: <math>f(n) = O(g(n))</math>~~
−
−
−	~~Solution: <math>n^2</math> outgrows n. We ignore <math>2\sqrt{n}</math> since <math>n</math> outgrows <math>\sqrt{n}</math>.~~
−
−
−	~~=='''3.''' <math>f(n) = n * log (n) </math>; <math>g(n) = \frac{n \sqrt{n}}{2}</math>==~~
−
−	~~Answer: <math>f(n) = O(g(n))</math>~~
−
−
−	~~Solution: Both sides have a factor of <math>n</math>, so we ignore it. <math>\sqrt{n}</math> outgrows <math>log(n)</math>, so <math>g(n)</math> is bigger.~~
−
−
−	~~=='''4.''' <math>f(n) = n + log(n)</math>; <math>g(n) = \sqrt{n}</math>==~~
−
−	~~Answer: <math>g(n) = O(f(n))</math>~~
−
−
−	~~Solution: <math>n</math> outgrows <math>\sqrt{n}</math>.~~
−
−
−	~~=='''5.''' <math>f(n) = 2 * log^2(n)</math>; <math>g(n) = log(n) + 1</math>==~~
−
−	~~Answer: <math>g(n) = O(f(n))</math>~~
−
−
−	~~Solution: <math>log^2(n)</math> grows faster than <math>log(n)</math>.~~
−
−	~~<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>~~
−
−
−	~~=='''6.''' <math>f(n) = 4n * log(n) + n</math>; <math>g(n) = \frac{n^2 - n}{2}</math>==~~
−
−	~~Answer: <math>f(n) = O(g(n))</math>~~
−
−
−	~~Solution: <math>n^2</math> outgrows <math>n * log(n)</math>.~~

@@ Line 1: / Line 1: @@
 =2-9.=
-For each of the following pairs of functions &lt;math&gt;f(n)&lt;/math&gt; and &lt;math&gt;g(n)&lt;/math&gt;, determine whether &lt;math&gt;f(n) = O(g(n))&lt;/math&gt;, &lt;math&gt;g(n) = O(f(n))&lt;/math&gt;, or both.
+For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>, determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both.
-=='''1.''' &lt;math&gt;f(n) = \frac{n^2 - n}{2}&lt;/math&gt;; &lt;math&gt;g(n) = 6 n&lt;/math&gt;==
+=='''1.''' <math>f(n) = \frac{n^2 - n}{2}</math>; <math>g(n) = 6 n</math>==
-Answer: &lt;math&gt;g(n) = O(f(n)) &lt;/math&gt;
+Answer: <math>g(n) = O(f(n)) </math>
-Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. &lt;math&gt;n^2&lt;/math&gt; outgrows &lt;math&gt;n&lt;/math&gt; as &lt;math&gt;n \rightarrow \infty&lt;/math&gt;. Therefore, &lt;math&gt;f(n)&lt;/math&gt; outgrows &lt;math&gt;g(n)&lt;/math&gt;.
+Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. <math>n^2</math> outgrows <math>n</math> as <math>n \rightarrow \infty</math>. Therefore, <math>f(n)</math> outgrows <math>g(n)</math>.
-=='''2.''' &lt;math&gt;f(n) = n + 2\sqrt{n}&lt;/math&gt;; &lt;math&gt;g(n) = n^2&lt;/math&gt;==
+=='''2.''' <math>f(n) = n + 2\sqrt{n}</math>; <math>g(n) = n^2</math>==
-Answer: &lt;math&gt;f(n) = O(g(n))&lt;/math&gt;
+Answer: <math>f(n) = O(g(n))</math>
-Solution: &lt;math&gt;n^2&lt;/math&gt; outgrows n. We ignore &lt;math&gt;2\sqrt{n}&lt;/math&gt; since &lt;math&gt;n&lt;/math&gt; outgrows &lt;math&gt;\sqrt{n}&lt;/math&gt;.
+Solution: <math>n^2</math> outgrows n. We ignore <math>2\sqrt{n}</math> since <math>n</math> outgrows <math>\sqrt{n}</math>.
-=='''3.''' &lt;math&gt;f(n) = n * log (n) &lt;/math&gt;; &lt;math&gt;g(n) = \frac{n \sqrt{n}}{2}&lt;/math&gt;==
+=='''3.''' <math>f(n) = n * log (n) </math>; <math>g(n) = \frac{n \sqrt{n}}{2}</math>==
-Answer: &lt;math&gt;f(n) = O(g(n))&lt;/math&gt;
+Answer: <math>f(n) = O(g(n))</math>
-Solution: Both sides have a factor of &lt;math&gt;n&lt;/math&gt;, so we ignore it. &lt;math&gt;\sqrt{n}&lt;/math&gt; outgrows &lt;math&gt;log(n)&lt;/math&gt;, so &lt;math&gt;g(n)&lt;/math&gt; is bigger.
+Solution: Both sides have a factor of <math>n</math>, so we ignore it. <math>\sqrt{n}</math> outgrows <math>log(n)</math>, so <math>g(n)</math> is bigger.
-=='''4.''' &lt;math&gt;f(n) = n + log(n)&lt;/math&gt;; &lt;math&gt;g(n) = \sqrt{n}&lt;/math&gt;==
+=='''4.''' <math>f(n) = n + log(n)</math>; <math>g(n) = \sqrt{n}</math>==
-Answer: &lt;math&gt;g(n) = O(f(n))&lt;/math&gt;
+Answer: <math>g(n) = O(f(n))</math>
-Solution: &lt;math&gt;n&lt;/math&gt; outgrows &lt;math&gt;\sqrt{n}&lt;/math&gt;.
+Solution: <math>n</math> outgrows <math>\sqrt{n}</math>.
-=='''5.''' &lt;math&gt;f(n) = 2 * log^2(n)&lt;/math&gt;; &lt;math&gt;g(n) = log(n) + 1&lt;/math&gt;==
+=='''5.''' <math>f(n) = 2 * log^2(n)</math>; <math>g(n) = log(n) + 1</math>==
-Answer: &lt;math&gt;g(n) = O(f(n))&lt;/math&gt;
+Answer: <math>g(n) = O(f(n))</math>
-Solution: &lt;math&gt;log^2(n)&lt;/math&gt; grows faster than &lt;math&gt;log(n)&lt;/math&gt;.
+Solution: <math>log^2(n)</math> grows faster than <math>log(n)</math>.
-&lt;math&gt;\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty&lt;/math&gt;
+<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>
-=='''6.''' &lt;math&gt;f(n) = 4n * log(n) + n&lt;/math&gt;; &lt;math&gt;g(n) = \frac{n^2 - n}{2}&lt;/math&gt;==
+=='''6.''' <math>f(n) = 4n * log(n) + n</math>; <math>g(n) = \frac{n^2 - n}{2}</math>==
-Answer: &lt;math&gt;f(n) = O(g(n))&lt;/math&gt;
+Answer: <math>f(n) = O(g(n))</math>
-Solution: &lt;math&gt;n^2&lt;/math&gt; outgrows &lt;math&gt;n * log(n)&lt;/math&gt;.
+Solution: <math>n^2</math> outgrows <math>n * log(n)</math>.

← Older revision		Revision as of 12:09, 2 August 2020
Line 1:		Line 1:
−	~~Fuck you matt~~,	+	=2-9.=
		+
		+	For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>, determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both.
		+
		+	=='''1.''' <math>f(n) = \frac{n^2 - n}{2}</math>; <math>g(n) = 6 n</math>==
		+
		+	Answer: <math>g(n) = O(f(n)) </math>
		+
		+
		+	Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. <math>n^2</math> outgrows <math>n</math> as <math>n \rightarrow \infty</math>. Therefore, <math>f(n)</math> outgrows <math>g(n)</math>.
		+
		+
		+	=='''2.''' <math>f(n) = n + 2\sqrt{n}</math>; <math>g(n) = n^2</math>==
		+
		+	Answer: <math>f(n) = O(g(n))</math>
		+
		+
		+	Solution: <math>n^2</math> outgrows n. We ignore <math>2\sqrt{n}</math> since <math>n</math> outgrows <math>\sqrt{n}</math>.
		+
		+
		+	=='''3.''' <math>f(n) = n * log (n) </math>; <math>g(n) = \frac{n \sqrt{n}}{2}</math>==
		+
		+	Answer: <math>f(n) = O(g(n))</math>
		+
		+
		+	Solution: Both sides have a factor of <math>n</math>, so we ignore it. <math>\sqrt{n}</math> outgrows <math>log(n)</math>, so <math>g(n)</math> is bigger.
		+
		+
		+	=='''4.''' <math>f(n) = n + log(n)</math>; <math>g(n) = \sqrt{n}</math>==
		+
		+	Answer: <math>g(n) = O(f(n))</math>
		+
		+
		+	Solution: <math>n</math> outgrows <math>\sqrt{n}</math>.
		+
		+
		+	=='''5.''' <math>f(n) = 2 * log^2(n)</math>; <math>g(n) = log(n) + 1</math>==
		+
		+	Answer: <math>g(n) = O(f(n))</math>
		+
		+
		+	Solution: <math>log^2(n)</math> grows faster than <math>log(n)</math>.
		+
		+	<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>
		+
		+
		+	=='''6.''' <math>f(n) = 4n * log(n) + n</math>; <math>g(n) = \frac{n^2 - n}{2}</math>==
		+
		+	Answer: <math>f(n) = O(g(n))</math>
		+
		+
		+	Solution: <math>n^2</math> outgrows <math>n * log(n)</math>.

← Older revision	Revision as of 01:00, 1 August 2020
Line 1:	Line 1:
	+	=2-9.=

	+	For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>, determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both.
	+
	+	=='''1.''' <math>f(n) = \frac{n^2 - n}{2}</math>; <math>g(n) = 6 n</math>==
	+
	+	Answer: <math>g(n) = O(f(n)) </math>
	+
	+
	+	Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. <math>n^2</math> outgrows <math>n</math> as <math>n \rightarrow \infty</math>. Therefore, <math>f(n)</math> outgrows <math>g(n)</math>.
	+
	+
	+	=='''2.''' <math>f(n) = n + 2\sqrt{n}</math>; <math>g(n) = n^2</math>==
	+
	+	Answer: <math>f(n) = O(g(n))</math>
	+
	+
	+	Solution: <math>n^2</math> outgrows n. We ignore <math>2\sqrt{n}</math> since <math>n</math> outgrows <math>\sqrt{n}</math>.
	+
	+
	+	=='''3.''' <math>f(n) = n * log (n) </math>; <math>g(n) = \frac{n \sqrt{n}}{2}</math>==
	+
	+	Answer: <math>f(n) = O(g(n))</math>
	+
	+
	+	Solution: Both sides have a factor of <math>n</math>, so we ignore it. <math>\sqrt{n}</math> outgrows <math>log(n)</math>, so <math>g(n)</math> is bigger.
	+
	+
	+	=='''4.''' <math>f(n) = n + log(n)</math>; <math>g(n) = \sqrt{n}</math>==
	+
	+	Answer: <math>g(n) = O(f(n))</math>
	+
	+
	+	Solution: <math>n</math> outgrows <math>\sqrt{n}</math>.
	+
	+
	+	=='''5.''' <math>f(n) = 2 * log^2(n)</math>; <math>g(n) = log(n) + 1</math>==
	+
	+	Answer: <math>g(n) = O(f(n))</math>
	+
	+
	+	Solution: <math>log^2(n)</math> grows faster than <math>log(n)</math>.
	+
	+	<math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math>
	+
	+
	+	=='''6.''' <math>f(n) = 4n * log(n) + n</math>; <math>g(n) = \frac{n^2 - n}{2}</math>==
	+
	+	Answer: <math>f(n) = O(g(n))</math>
	+
	+
	+	Solution: <math>n^2</math> outgrows <math>n * log(n)</math>.