× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS

Nested Loop: How to Calculate its Time Complexity

Asad Saeeduddin
Oct 08, 2015
<p>The outer loop will run while i^2&lt; N, or equivalently while i&lt; sqrt(N). This means the outer loop will run sqrt(N) times.</p> <p>The inner loop will run while j^2&lt; N^2, or equivalently while j&lt; N. This means the inner loop will run N times (for each iteration of the outer loop).</p> <p>The total number of iterations is therefore (N^0.5)*N=N^(3/2).</p> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/29884663/Calculating%20the%20time%20complexity%20of%20nested%20loop/29884713">Stack Overflow</a>.</p>
comments powered by Disqus