Blogs Hub

by AskGif | Jul 16, 2018 | Category :coding

What is Asymptotic Analysis and how to calculate it?

What is Asymptotic Analysis and how to calculate it?

<p>In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.</p> <p>As an illustration, suppose that we are interested in the properties of a function f(n) as n becomes very large. If f(n) = n^2 + 3n, then as n becomes very large, the term 3n becomes insignificant compared to n^2. The function f(n) is said to be "asymptotically equivalent to n^2, as n &rarr; &infin;". This is often written symbolically as f(n) ~ n^2, which is read as "f(n) is asymptotic to n^2".</p> <p>&nbsp;</p> <p><strong>Guidelines for Asymptotic Analysis</strong></p> <p>&nbsp;</p> <p>1) <strong>Loops</strong>: The running time of a loop is, at most, the running time of the statements inside the loop (including tests) multiplied by the number of iterations.</p> <pre class="language-java"><code>//n times execution for(int i=0;i&lt;=n;i++) { n = n + 5; // constant time c } Total time = c x n = cn = O(n)</code></pre> <p>&nbsp;</p> <p>&nbsp;</p> <p>2) <strong>Nested loops</strong>: Analyze from the inside out. Total running time is the product of the sizes of all the loops.</p> <pre class="language-java"><code>//outer loop executes n times for(int i=0;i&lt;n;i++) { //inner loop executes n times for(int j=0;j&lt;n;j++) { n = n + 5; // constant time c } } Total time = c x n x n = cn^2 = O(n^2)</code></pre> <p>&nbsp;</p> <p>3) <strong>Logarithmic complexity</strong>: An algorithm is O(logn) if it takes a constant time to cut the problem size by a fraction (usually by 1/2). As an example let us consider the following example:</p> <pre class="language-java"><code>for(int i=0;i&lt;n;) { i = i*2; }</code></pre> <p>On careful observation, the value of i is doubling every time. Initially i = 1, in next step i = 2, and in subsequent steps i =4, 8 and so on.</p> <pre class="language-markup"><code>Now we have 2^k = n taking log on both sides log(2^k) = logn klog2 = logn k = logn // assuming base is 2 Total time = O(logn)</code></pre>

read more...