https://wiki.kram.nz/index.php?action=history&feed=atom&title=Example_3 2026-04-28T13:09:37Z Revision history for this page on the wiki MediaWiki 1.45.3 https://wiki.kram.nz/index.php?title=Example_3&diff=780&oldid=prev 2008-11-03T05:07:59Z

<p>2 revision(s)</p> <p><b>New page</b></p><div>====Example 3====<br /> <br /> Show that &quot;&#039;&#039;f(n) is Θ(n^2)&#039;&#039;&quot; when &quot;&#039;&#039;f(n) = 5 * n(n + 100)&#039;&#039;&quot;.<br /> <br /> <br /> To show that &#039;&#039;f(n) is Θ(n^2)&#039;&#039;, we have to show that &#039;&#039;f(n) = O(g(n))&#039;&#039; and &#039;&#039;f(n) = Ω(g(n))&#039;&#039;.<br /> <br /> We have already shown that &#039;&#039;f(n) = O(g(n))&#039;&#039; in example 1, so now we&#039;ll focus on the second part.<br /> <br /> Firstly, notice that &#039;&#039;f(n) = Ω(g(n))&#039;&#039; is the same as &#039;&#039;g(n) = O(f(n))&#039;&#039;. We will show that the second statement is true.<br /> <br /> &#039;&#039;( n^2 ) ≤ C * ( n ( n + 100 ) )&#039;&#039;<br /> <br /> If we choose C to be 2, then: &#039;&#039;( n^2 ) ≤ 2 * ( n^2 + 100*n )&#039;&#039;<br /> <br /> Rearranging gives: &#039;&#039;0 ≤ n^2 + 100*n&#039;&#039;<br /> <br /> So the solutions to the equations are &#039;&#039;n ≥ 0&#039;&#039; and &#039;&#039;n ≥ 100&#039;&#039;.<br /> <br /> &quot;&#039;&#039;g(n) ≤ C * f(n)&#039;&#039;&quot; is true when &#039;&#039;C = 2&#039;&#039; and &#039;&#039;n0 ≥ 0&#039;&#039;.<br /> <br /> Since it is possible to find a set of constant values for &#039;&#039;C&#039;&#039; and &#039;&#039;n0&#039;&#039;, such that &#039;&#039;g(n) ≤ C * f(n)&#039;&#039; (when &#039;&#039;n ≥ n0&#039;&#039; ), we show that &#039;&#039;f(n) is O(n^2)&#039;&#039;.</div>

Mark