Big O Notation: Understanding Time Complexity using Flowcharts

I highly recommend Edison's post on Big-O complexity in JavaScript. It's the friendliest article I've seen on the topic.

Article No Longer Available

I'll be taking points from Edison here as I visualize Big-O time complexity with flowcharts.

O log(n)

Logarithmic Time

The way I visually understand time complexity is by looking at the iterator, i*2 for example , and looking at how many loops the function has.

O(n)

Linear Time



Linear time and logarithmic time look similar but the output is different because of the conditions of the loop. exampleLogarithmic(100) will return 1, 2, 4, 8, 16, 32, 64, whereas exampleLinear(100) simply loops through all positive integers under 100.

O(n^2)

Quadratic Time



The number of loops coincides with the exponent which n is raised to. You can literally see the function grow bigger as time complexity increases.

O(n^3)

Cubic Time



This isn't the only way to understand time complexity, but it is really helpful to literally see the function grow longer as time complexity increases. Sometimes code written in black and white

 blocks doesn't get the point across to visual learners.

<p>Now let's have a quiz. What is the time complexity of this function?</p>

<p>Make your guess...<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046526425.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
It's linear! I can tell because there's one loop and the iterator doesn't cause the loop to skip over any integers.</p>

<p>What is the time complexity of this function?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046682236.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
Don't doubt yourself. Although this is a bit different from the first examples, it has linear time complexity.</p>

<p>What is the time complexity of this function?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046719860.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
You may see a pattern here. It's linear!</p><p>Now, if you've been following my train of logic, this may be a trick question:<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046876014.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"></p>

<p>I said that the number of loops denoted the exponent n is raised to. So why is does this have linear time complexity and not quadratic?</p>

<p>This would have quadratic time complexity if it showed a for loop inside of another for loop. However, one for loop that runs <em>after</em> another for loop does not have quadratic but rather linear time complexity.</p>

<p>Okay, so what is the time complexity of this function?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046913700.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
There's nothing tricky here. This has quadratic time complexity.</p>

<p>Now, for your last question - a question that questions all the other questions - what is this function's time complexity?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601047060673.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
I hope you're looking at the conditions of the for loop as well as the sheer number of loops. This has quadratic time complexity because of the loop condition i<n>

<p>I generated the images in this post with my app, whose development process I described in another post:</p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601047160481.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts">[</p>

<h2>
  
  
  How to get 100 on Lighthouse
</h2>

<h3>
  
  
  ender minyard ・ Aug 30 '20 ・ 2 min read
</h3>

<h2>
  
  
  webperf#speed#javascript#webdev
</h2>

<p>](/ender_minyard/how-i-got-100-on-lighthouse-2icd)</p>


          

            
        </n></p>

The above is the detailed content of Big O Notation: Understanding Time Complexity using Flowcharts. For more information, please follow other related articles on the PHP Chinese website!