Big O Notation? More like Big O-M-G

Big O Notation? More like Big O-M-G

<div style="margin: 5px 5% 10px 5%;"><img src="http://www.sickgaming.net/blog/wp-content/uploads/2018/07/big-o-notation-more-like-big-o-m-g.jpg" width="1718" height="1075" title="" alt="" /></div><div><div><img src="http://www.sickgaming.net/blog/wp-content/uploads/2018/07/big-o-notation-more-like-big-o-m-g.jpg" class="ff-og-image-inserted" /></div>
<blockquote class="graf graf--blockquote graf--leading">
<p>Time Complexity: <code class="markup--code markup--blockquote-code">O(n^2)</code></p>
</blockquote>
<p class="graf graf--p graf-after--blockquote">In this next scenario, let’s say that only one person knows who took your cookie and only by name. The person who took the cookie won’t fess up to it either, so you have to name off each other friend to the friend you are talking to. This can be written <em class="markup--em markup--p-em">in Python3</em>:</p>
<pre class="graf graf--pre graf-after--p">
&gt;&gt;&gt; def who_has_my_cookie(my_friends):
... for friend in my_friends:
... for their_friend in friend.get('friends'):
... if their_friend.get('has_cookie'):
... return their_friend.get('name')</pre>
<p class="graf graf--p graf-after--pre">If you imagine yourself in this situation you can see that it’s going to take a lot longer than any of the other situations because you need to keep reciting everyone’s name every time you go to the next friend.Worst case scenario, you need to cycle through each friend and ask them about every other friend. If you look at the loops, you can see that the outer loop has a time complexity of <code class="markup--code markup--p-code">O(n)</code>, and the inner loop also has a time complexity of <code class="markup--code markup--p-code">O(n)</code>. This means the function will have a time complexity of <code class="markup--code markup--p-code">O(n^2)</code> because you multiply the time complexities together <code class="markup--code markup--p-code">O(n * n)</code>.</p>
<p class="graf graf--p graf-after--p">Let’s feed this function some input and see who took your cookie:</p>
<pre class="graf graf--pre graf-after--p">
&gt;&gt;&gt; my_friends = [
... {'name':'Steven', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Binita', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Linds', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Raman', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Elaine', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':True},
... {'name':'Elaine', 'has_cookie':False}
... ]
... }
... ]
&gt;&gt;&gt; cookie_taker = who_has_my_cookie(my_friends)
&gt;&gt;&gt; print(cookie_taker)
Raman</pre>
<p class="graf graf--p graf-after--pre graf--trailing"><em class="markup--em markup--p-em">Summary of </em><code class="markup--code markup--p-code"><em class="markup--em markup--p-em">O(n^2)</em></code><em class="markup--em markup--p-em">:</em> There is a loop within a loop, so you could instantly think that it would be <code class="markup--code markup--p-code">O(n^2)</code>. That’s a correct assumption, but to make sure, double check and make sure the increments are still being incremented <code class="markup--code markup--p-code">n</code>times. <em class="markup--em markup--p-em">Some loops within loops turn out to be </em><code class="markup--code markup--p-code"><em class="markup--em markup--p-em">O(nlog(n))</em></code>.</p>
</div>