Difference between revisions of "TADM2E 2.23"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
 
Line 1: Line 1:
 
=2-23.=
 
=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?  ==
+
== 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.  
 
Answer: Yes.  
Line 8: Line 8:
 
Explanation:  
 
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.
 
Answer: Yes.
Line 18: Line 18:
 
Explanation:
 
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.
 
Answer: Yes.
Line 28: Line 28:
 
Explanation:
 
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.
 
Answer: No.
Line 38: Line 38:
 
Explanation:
 
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.
 
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>.

Latest revision as of 18:23, 11 September 2014

2-23.

If I prove that an algorithm takes $ O(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on some inputs?

Answer: Yes.


Explanation:

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


If I prove that an algorithm takes $ O(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on all inputs?

Answer: Yes.


Explanation:

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


If I prove that an algorithm takes $ \Theta(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on some inputs?

Answer: Yes.


Explanation:

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


If I prove that an algorithm takes $ \Theta(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on all inputs?

Answer: No.


Explanation:

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


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

Answer: Yes.


Explanation: Both even and odd functions are $ \Theta(n^2) $.