https://wiki.kram.nz/index.php?action=history&feed=atom&title=Example_1 2026-04-27T09:56:33Z Revision history for this page on the wiki MediaWiki 1.45.3 https://wiki.kram.nz/index.php?title=Example_1&diff=775&oldid=prev 2008-11-03T05:07:59Z

<p>4 revision(s)</p> <p><b>New page</b></p><div>====Example 1==== <br /> <br /> Show that &quot;&#039;&#039; f(n) is O(n^2)&#039;&#039;&quot; when &quot;&#039;&#039;f(n) = 5 * n(n + 100)&#039;&#039;&quot;.<br /> <br /> <br /> To do this, we have to show that &#039;&#039; f(n) ≤ C * (n^2)&#039;&#039; (or equivalently, &#039;&#039; 5 * n(n + 100) ≤ C * (n^2) &#039;&#039; - as per the definition) when n is bigger than the value n0 (which we will determine).<br /> <br /> We might do this by first arbitrarily picking a value of C or n0. If, for example we choose c = 10, then the equation becomes <br /> <br /> &#039;&#039; 5 * n(n + 100) ≤ 10 * (n^2) &#039;&#039; simplified, giving &#039;&#039; n(n + 100) ≤ 2 * (n^2) &#039;&#039;<br /> <br /> Now, we just have find a value of n0, whereby when &#039;&#039; n0 ≤ n &#039; the inequality becomes true.<br /> <br /> In this case, if we solve the inequality for &#039;&#039; n, n ≤ 0 or n ≥ 100 &#039;&#039;. So, when &#039;&#039; n ≥ 100 &#039;&#039;, the inequality is true, and we can give &#039;&#039;n0&#039;&#039; ANY value that is bigger than 100.<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; f(n) ≤ C * g(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