Difference between revisions of "TADM2E 2.9"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
Line 1: Line 1:
 
=2-9.=
 
=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.
+
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>.

Revision as of 18:23, 11 September 2014

2-9.

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

1. $ f(n) = \frac{n^2 - n}{2} $; $ g(n) = 6 n $

Answer: $ g(n) = O(f(n)) $


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


2. $ f(n) = n + 2\sqrt{n} $; $ g(n) = n^2 $

Answer: $ f(n) = O(g(n)) $


Solution: $ n^2 $ outgrows n. We ignore $ 2\sqrt{n} $ since $ n $ outgrows $ \sqrt{n} $.


3. $ f(n) = n * log (n) $; $ g(n) = \frac{n \sqrt{n}}{2} $

Answer: $ f(n) = O(g(n)) $


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


4. $ f(n) = n + log(n) $; $ g(n) = \sqrt{n} $

Answer: $ g(n) = O(f(n)) $


Solution: $ n $ outgrows $ \sqrt{n} $.


5. $ f(n) = 2 * log^2(n) $; $ g(n) = log(n) + 1 $

Answer: $ g(n) = O(f(n)) $


Solution: $ log^2(n) $ grows faster than $ log(n) $.

$ \lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty $


6. $ f(n) = 4n * log(n) + n $; $ g(n) = \frac{n^2 - n}{2} $

Answer: $ f(n) = O(g(n)) $


Solution: $ n^2 $ outgrows $ n * log(n) $.

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_2.9&oldid=174"