TADM2E 2.23 - Revision history

Matt: Undo revision 1178 by FuckyouMatt (talk)

2020-08-04T20:13:01Z

Undo revision 1178 by FuckyouMatt (talk)

FuckyouMatt: Replaced content with "MATT!!! VS FUCKYOUMATT!!!!!!!!!!!!!!!!!"

2020-08-04T01:33:10Z

Replaced content with "MATT!!! VS FUCKYOUMATT!!!!!!!!!!!!!!!!!"

Algowikiadmin: Recovering wiki

2014-09-11T18:23:40Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:03Z

Recovering wiki

New page

=2-23.=

== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? ==

Answer: Yes.

Explanation:

<math>O(n^2)</math> worst-case means that the worst-case is bound from above by <math>O(n^2)</math>; it does not necessarily mean that all cases must follow that complexity. Thus, there could be some inputs that are <math>O(n)</math>.

== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? ==

Answer: Yes.

Explanation:

<math>O(n^2)</math> worst-case is only an upper bound on the worst-case. It is possible that all inputs can be done in <math>O(n)</math>, which still follows this upper bound.

== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? ==

Answer: Yes.

Explanation:

Although the worst case is <math>\Theta(n^2)</math>, this does not mean all cases are <math>\Theta(n^2)</math>.

== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? ==

Answer: No.

Explanation:

The worst-case input must follow <math>\Theta(n^2)</math>, so it can't be <math>O(n)</math>. Therefore, all cases are not <math>O(n)</math>

== Is the function <math>f(n) = \Theta(n^2)</math>, where <math>f(n) = 100n^2</math> for even <math>n</math> and <math>f(n) = 20n^{2} - n * log_2 n</math> for odd <math>n</math>? ==

Answer: Yes.

Explanation: Both even and odd functions are <math>\Theta(n^2)</math>.

← Older revision		Revision as of 01:33, 4 August 2020
Line 1:		Line 1:
−	~~=2-23.=~~	+	MATT!!! VS FUCKYOUMATT!!!!!!!!!!!!!!!!!
−
−	~~== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? ==~~
−
−	~~Answer: Yes.~~
−
−
−	~~Explanation:~~
−
−	<math>O(n^2)</math> worst-case means that the worst-case is bound from above by <math>O(n^2)</math>; it does not necessarily mean that all cases must follow that complexity. Thus, there could be some inputs that are <math>O(n)</math>.
−
−
−	~~== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? ==~~
−
−	~~Answer: Yes.~~
−
−
−	~~Explanation:~~
−
−	~~<math>O(n^2)</math> worst-case is only an upper bound on the worst-case. It is possible that all inputs can be done in <math>O(n)</math>, which still follows this upper bound.~~
−
−
−	~~== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? ==~~
−
−	~~Answer: Yes.~~
−
−
−	~~Explanation:~~
−
−	~~Although the worst case is <math>\Theta(n^2)</math>, this does not mean all cases are <math>\Theta(n^2)</math>.~~
−
−
−	~~== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? ==~~
−
−	~~Answer: No.~~
−
−
−	~~Explanation:~~
−
−	~~The worst-case input must follow <math>\Theta(n^2)</math>, so it can't be <math>O(n)</math>. Therefore, all cases are not <math>O(n)</math>~~
−
−
−	~~== Is the function <math>f(n) = \Theta(n^2)</math>, where <math>f(n) = 100n^2</math> for even <math>n</math> and <math>f(n) = 20n^{2} - n * log_2 n</math> for odd <math>n</math>? ==~~
−
−	~~Answer: Yes.~~
−
−
−	~~Explanation: Both even and odd functions are <math>\Theta(n^2)</math>.~~

← Older revision		Revision as of 20:13, 4 August 2020
Line 1:		Line 1:
−	~~MATT!!! VS FUCKYOUMATT!!!!!!!!!!!!!!!!!~~	+	=2-23.=
		+
		+	== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? ==
		+
		+	Answer: Yes.
		+
		+
		+	Explanation:
		+
		+	<math>O(n^2)</math> worst-case means that the worst-case is bound from above by <math>O(n^2)</math>; it does not necessarily mean that all cases must follow that complexity. Thus, there could be some inputs that are <math>O(n)</math>.
		+
		+
		+	== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? ==
		+
		+	Answer: Yes.
		+
		+
		+	Explanation:
		+
		+	<math>O(n^2)</math> worst-case is only an upper bound on the worst-case. It is possible that all inputs can be done in <math>O(n)</math>, which still follows this upper bound.
		+
		+
		+	== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? ==
		+
		+	Answer: Yes.
		+
		+
		+	Explanation:
		+
		+	Although the worst case is <math>\Theta(n^2)</math>, this does not mean all cases are <math>\Theta(n^2)</math>.
		+
		+
		+	== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? ==
		+
		+	Answer: No.
		+
		+
		+	Explanation:
		+
		+	The worst-case input must follow <math>\Theta(n^2)</math>, so it can't be <math>O(n)</math>. Therefore, all cases are not <math>O(n)</math>
		+
		+
		+	== Is the function <math>f(n) = \Theta(n^2)</math>, where <math>f(n) = 100n^2</math> for even <math>n</math> and <math>f(n) = 20n^{2} - n * log_2 n</math> for odd <math>n</math>? ==
		+
		+	Answer: Yes.
		+
		+
		+	Explanation: Both even and odd functions are <math>\Theta(n^2)</math>.

@@ Line 1: / Line 1: @@
 =2-23.=
-== If I prove that an algorithm takes &lt;math&gt;O(n^2)&lt;/math&gt; worst-case time, is it possible that it takes &lt;math&gt;O(n)&lt;/math&gt; on ''some'' inputs?  ==
+== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs?  ==
 Answer: Yes.
@@ Line 8: / Line 8: @@
 Explanation:
-&lt;math&gt;O(n^2)&lt;/math&gt; worst-case means that the worst-case is bound from above by &lt;math&gt;O(n^2)&lt;/math&gt;; it does not necessarily mean that all cases must follow that complexity. Thus, there could be some inputs that are &lt;math&gt;O(n)&lt;/math&gt;.
+<math>O(n^2)</math> worst-case means that the worst-case is bound from above by <math>O(n^2)</math>; it does not necessarily mean that all cases must follow that complexity. Thus, there could be some inputs that are <math>O(n)</math>.
-== If I prove that an algorithm takes &lt;math&gt;O(n^2)&lt;/math&gt; worst-case time, is it possible that it takes &lt;math&gt;O(n)&lt;/math&gt; on ''all'' inputs? ==
+== If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? ==
 Answer: Yes.
@@ Line 18: / Line 18: @@
 Explanation:
-&lt;math&gt;O(n^2)&lt;/math&gt; worst-case is only an upper bound on the worst-case. It is possible that all inputs can be done in &lt;math&gt;O(n)&lt;/math&gt;, which still follows this upper bound.
+<math>O(n^2)</math> worst-case is only an upper bound on the worst-case. It is possible that all inputs can be done in <math>O(n)</math>, which still follows this upper bound.
-== If I prove that an algorithm takes &lt;math&gt;\Theta(n^2)&lt;/math&gt; worst-case time, is it possible that it takes &lt;math&gt;O(n)&lt;/math&gt; on ''some'' inputs?   ==
+== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs?   ==
 Answer: Yes.
@@ Line 28: / Line 28: @@
 Explanation:
-Although the worst case is &lt;math&gt;\Theta(n^2)&lt;/math&gt;, this does not mean all cases are &lt;math&gt;\Theta(n^2)&lt;/math&gt;.
+Although the worst case is <math>\Theta(n^2)</math>, this does not mean all cases are <math>\Theta(n^2)</math>.
-== If I prove that an algorithm takes &lt;math&gt;\Theta(n^2)&lt;/math&gt; worst-case time, is it possible that it takes &lt;math&gt;O(n)&lt;/math&gt; on ''all'' inputs?  ==
+== If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs?  ==
 Answer: No.
@@ Line 38: / Line 38: @@
 Explanation:
-The worst-case input must follow &lt;math&gt;\Theta(n^2)&lt;/math&gt;, so it can't be &lt;math&gt;O(n)&lt;/math&gt;. Therefore, all cases are not &lt;math&gt;O(n)&lt;/math&gt;
+The worst-case input must follow <math>\Theta(n^2)</math>, so it can't be <math>O(n)</math>. Therefore, all cases are not <math>O(n)</math>
-== Is the function &lt;math&gt;f(n) = \Theta(n^2)&lt;/math&gt;, where &lt;math&gt;f(n) = 100n^2&lt;/math&gt; for even &lt;math&gt;n&lt;/math&gt; and &lt;math&gt;f(n) = 20n^{2} - n * log_2 n&lt;/math&gt; for odd &lt;math&gt;n&lt;/math&gt;?  ==
+== Is the function <math>f(n) = \Theta(n^2)</math>, where <math>f(n) = 100n^2</math> for even <math>n</math> and <math>f(n) = 20n^{2} - n * log_2 n</math> for odd <math>n</math>?  ==
 Answer: Yes.
-Explanation: Both even and odd functions are &lt;math&gt;\Theta(n^2)&lt;/math&gt;.
+Explanation: Both even and odd functions are <math>\Theta(n^2)</math>.