05-22-2020, 09:40 PM
Complexity of Python Operations
<div><figure class="wp-block-embed-wordpress wp-block-embed is-type-video is-provider-youtube">
<div class="wp-block-embed__wrapper">
<div class="ast-oembed-container"><iframe title="Big-O Runtime Complexity List and Set Operations" width="1400" height="788" src="https://www.youtube.com/embed/SmutQEAp1w8?feature=oembed" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe></div>
</div>
</figure>
<p>In this tutorial, you’ll learn the runtime complexity of different Python operations. </p>
<p>Then, you’ll learn how to calculate the complexity of your own function by combining the complexity classes of its constituents. This is called <em>“static analysis”</em> </p>
<p>The tutorial is loosely based on (<a rel="noreferrer noopener" href="https://www.ics.uci.edu/~brgallar/week8_2.html" target="_blank">source</a>) but it extends it significantly with more practical examples, interactive snippets, and explanatory material.</p>
<h2>Introducing Big-O</h2>
<p><strong>Definition</strong>: The complexity of an operation (or an algorithm for that matter) is the number of resources that are needed to run it (<a rel="noreferrer noopener" href="https://en.wikipedia.org/wiki/Computational_complexity" target="_blank">source</a>). Resources can be time (<em>runtime complexity</em>) or space (<em>memory complexity</em>). </p>
<p>So, how can you measure the complexity of an algorithm? In most cases, the complexity of an algorithm is not static. It varies with the size of the input to the algorithm or the operation. </p>
<p>For example, the <a rel="noreferrer noopener" href="https://blog.finxter.com/python-list-sort/" target="_blank">list method <code>list.sort()</code></a> has one input argument: the list object to be sorted. The runtime complexity is not constant, it increases with increasing size of the list. If there are more elements to be sorted, the runtime of the algorithm increases. </p>
<h3>Complexity Function</h3>
<p>Given input size <em><code>n</code></em>, you can describe the complexity of your algorithm with a function of the input <code><em>n</em> → <em>f</em>(<em>n</em>)</code> that defines the number of “resource units” (e.g., time, memory) needed to finish it (worst-case or average-case). </p>
<p>Say, you’ve got three implementations to <a rel="noreferrer noopener" href="https://blog.finxter.com/how-to-sort-a-list-alphabetically-in-python/" target="_blank">sort a list</a>: <code>implementation_1</code>, <code>implementation_2</code>, <code>implementation_3</code>. </p>
<figure class="wp-block-image size-large"><img src="https://blog.finxter.com/wp-content/uploads/2020/05/image-63.png" alt="" class="wp-image-8717" srcset="https://blog.finxter.com/wp-content/uploads/2020/05/image-63.png 736w, https://blog.finxter.com/wp-content/uplo...00x226.png 300w" sizes="(max-width: 736px) 100vw, 736px" /></figure>
<p>The figure shows the three complexity functions. The x axis measures the input size (in our example, it would be the list size). The y axis measures the complexity with respect to this input.</p>
<ul>
<li><code>implementation_1</code> has a quadratic complexity function <em>f(n) = n²</em>. </li>
<li><code>implementation_2</code> has a quadratic complexity function <em>f(n) = 2n²</em>.</li>
<li><code>implementation_3</code> has a logarithmic complexity function <em>f(n) = n log(n)</em>.</li>
</ul>
<p>You can see the code we used to generate this plot here:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">import matplotlib.pyplot as plt
import math implementation_1 = [n**2 for n in range(1, 100, 10)]
implementation_2 = [2*n**2 for n in range(1, 100, 10)]
implementation_3 = [n*math.log(n) for n in range(1, 100, 10)] plt.plot(implementation_1, '--.', label='implementation 1')
plt.plot(implementation_2, '-o', label='implementation 2')
plt.plot(implementation_3, '-x', label='implementation 3') plt.legend()
plt.xlabel('Input (ex: List Size)')
plt.ylabel('Complexity (ex: Runtime)')
plt.grid()
plt.show()</pre>
<p>Of course, it’s good to waste as little resources as possible so the logarithmic complexity function is superior to the quadratic complexity functions.</p>
<h3>Big-O Notation</h3>
<p>For large inputs, the runtime behavior will be dominated by the part of the complexity function that grows fastest. For example, a quadratic runtime complexity function <em>f(n) = 1000n² + 100000n + 999</em> will be much better than a cubic runtime complexity function <em>g(n) = 0.1n³</em>. </p>
<p>Why? Because sooner or later the function <em>g(n)</em> will produce much higher values than <em>f(n)</em> as the input size n increases.</p>
<p>In fact, you can argue that the only important part of a complexity function is the part that grows fastest with increasing input size.</p>
<p>This is exactly what’s the Big-O notation is all about:</p>
<p><strong><em>The </em></strong><em><strong>Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.</strong></em> (<a rel="noreferrer noopener" href="https://en.wikipedia.org/wiki/Big_O_notation" target="_blank">wiki</a>)</p>
<p>Roughly speaking, you remove everything but the fastest-growing term from the complexity function. This allows you to quickly compare different algorithms against each other.</p>
<p>To show this, have a look at our two examples:</p>
<ul>
<li>Complexity function <em>f(n) = 1000n² + 100000n + 999</em> grows like <em>O(n²)</em>.</li>
<li>Complexity function <em>g(n) = 0.1n³</em> grows like <em>O(n³)</em>. </li>
</ul>
<p>By reducing the complexity function to its asymptotic growth, you can immediately see that the former is superior to the latter in terms of runtime complexity—without being distracted by all the constant factors in front of the constituents or the constituents with smaller asymptotic growth.</p>
<h3>Examples Big-O of Complexity Functions</h3>
<p>So, here are a few examples of complexity functions and their asymptotic growth in Big-O notation:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Complexity Function</th>
<th>Asymptotic Growth</th>
</tr>
</thead>
<tbody>
<tr>
<td><em>f(n) = 10000</em></td>
<td><em>O(<em>1</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = n + 1000000</em></td>
<td><em>O(<em>n</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = 33n + log(n)</em></td>
<td><em>O(<em>n</em> log(n))</em></td>
</tr>
<tr>
<td><em>f(n) = 33n + 4n * log(n)</em></td>
<td><em>O(<em>n</em> log(n))</em></td>
</tr>
<tr>
<td><em>f(n) = n² + n</em></td>
<td><em>O(<em>n²</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = 1000n² + 100000n + 999</em></td>
<td><em>O(<em>n²</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = 0.000000001n³ + 4n² + 100000n + 999</em></td>
<td><em>O(<em>n³</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = n * n³ + 33n</em></td>
<td><em>O(<em>n³</em>)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>You can see that the asymptotic growth of a function (in Big-O notation) is dominated by the fastest-growing term in the function equation.</p>
<h2>Python Complexity of Operations</h2>
<p>Let’s explore the complexity of Python operations—classified by the data structure on which you perform those operations. A great coder will always use the data structure that suits their needs best. </p>
<p>In general, the list data structure supports more operations than the set data structure as it keeps information about the ordering of the elements—at the cost of higher computational complexity.</p>
<h3>Python List Complexity</h3>
<p>Assume that the length of the data type is defined as <code>n</code> (that is—<code>n = len(data_type)</code>). You can now categorize the asymptotic complexity of the different complexity functions as follows:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Operation</th>
<th>Example</th>
<th>Complexity</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://blog.finxter.com/python-list-index/" target="_blank" rel="noreferrer noopener">Index</a></td>
<td><code>l[i]</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/resolve-indexerror-list-assignment-index-out-of-range/" target="_blank" rel="noreferrer noopener">Store</a></td>
<td><code>l[i] = 42</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-length-whats-the-runtime-complexity-of-len/" target="_blank" rel="noreferrer noopener">Length</a></td>
<td><code>len(l)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-append/" target="_blank" rel="noreferrer noopener">Append</a></td>
<td><code>l.append(42)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-pop/" target="_blank" rel="noreferrer noopener">Pop</a></td>
<td><code>l.pop()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-clear/" target="_blank" rel="noreferrer noopener">Clear</a></td>
<td><code>l.clear()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a rel="noreferrer noopener" href="https://blog.finxter.com/introduction-to-slicing-in-python/" target="_blank">Slicin</a><a href="https://blog.finxter.com/introduction-to-slicing-in-python/" target="_blank" rel="noreferrer noopener">g</a></td>
<td><code>l[a:b]</code></td>
<td><em>O(b-a)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-extend/" target="_blank" rel="noreferrer noopener">Extend</a></td>
<td><code>l1.extend(l2)</code></td>
<td><em>O(len(l1)+len(l2))</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">Constructor</a></td>
<td><code>list(iter)</code></td>
<td><em>O(len(iter))</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-string-contains/" target="_blank" rel="noreferrer noopener">Equality</a></td>
<td><code>l1 == l2</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-slice-assignment/" target="_blank" rel="noreferrer noopener">Slice Assign</a></td>
<td><code>l[a:b] = ...</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-remove/" target="_blank" rel="noreferrer noopener">Delete</a></td>
<td><code>del l[i]</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-remove/" target="_blank" rel="noreferrer noopener">Remove</a></td>
<td><code>l.remove(...)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">Membership</a></td>
<td><code>x in l</code> / <code>x not in l</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-copy/" target="_blank" rel="noreferrer noopener">Copy</a></td>
<td><code>l.copy()</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-pop/" target="_blank" rel="noreferrer noopener">Pop</a></td>
<td><code>l.pop(0)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/how-to-find-the-minimum-of-a-list-of-lists-in-python/" target="_blank" rel="noreferrer noopener">Min</a></td>
<td><code>min(l)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/how-to-find-the-max-of-list-of-lists-in-python/" target="_blank" rel="noreferrer noopener">Max</a></td>
<td><code>max(l)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-reverse/" target="_blank" rel="noreferrer noopener">Reverse</a></td>
<td><code>l.reverse()</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-loops/" target="_blank" rel="noreferrer noopener">Iterate</a></td>
<td><code>for x in l:</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-sort/" target="_blank" rel="noreferrer noopener">Sort</a></td>
<td><code>l.sort()</code></td>
<td><em>O(n log(n))</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-concatenation-add-vs-inplace-add-vs-extend/" target="_blank" rel="noreferrer noopener">Multiply</a></td>
<td><code>l*k</code></td>
<td><em>O(n k)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>Tuples are similar as lists—with a few exceptions: you cannot modify a tuple because they are immutable. </p>
<p>Let’s consider another important data structure:</p>
<h3>Python Set Complexity</h3>
<p>Assume that the length of the data type is defined as <code>n</code> (that is—<code>n = len(data_type)</code>). If there are two sets in a single operation such as <code>s1 == s2</code>, the lengths are given by the variables <code>n1</code> and <code>n2</code>. You can now categorize the asymptotic complexity of the different complexity functions as follows:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Operation</th>
<th>Example</th>
<th>Complexity</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Length</a></td>
<td><code>len(s)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Add</a></td>
<td><code>s.add(42)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><strong><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Membership</a></strong></td>
<td><strong><code>42 in s</code> / <code>42 not in s</code></strong></td>
<td><strong><em>O(1)</em></strong></td>
</tr>
<tr>
<td><strong><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Remove</a></strong></td>
<td><strong><code>s.remove(42)</code></strong></td>
<td><strong><em>O(1)</em></strong></td>
</tr>
<tr>
<td>Pop</td>
<td><code>s.pop()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td>Clear</td>
<td><code>s.clear()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td>Constructor</td>
<td><code>set(iter)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td>Equality</td>
<td><code>s1 == s2</code> / <code>s1 != s2</code></td>
<td><em>O(min(n1, n2))</em></td>
</tr>
<tr>
<td>Union</td>
<td><code>s1 | s2</code></td>
<td><em>O(n1+n2)</em></td>
</tr>
<tr>
<td>Intersection</td>
<td><code>s1 & s2</code></td>
<td><em>O(min(n1, n2))</em></td>
</tr>
<tr>
<td>Difference</td>
<td><code>s1 - s2</code></td>
<td><em>O(n2)</em></td>
</tr>
<tr>
<td>Symmetric Difference</td>
<td><code>s1 ^ s2</code></td>
<td><em>O(n1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-loops/" target="_blank" rel="noreferrer noopener">Iteration</a></td>
<td><code>for x in s:</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td>Copy</td>
<td><code>s.copy()</code></td>
<td><em>O(n)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>I highlighted the set operations that are more efficient than the corresponding list operations. The reason for those being O(1) rather than O(n) is that the <a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">list data structure</a> also maintains the ordering of the elements—which incurs additional overhead.</p>
<h3>Python Dictionary Complexity</h3>
<p>Now, have a look at the time complexity of Python dictionary operations:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Operation</th>
<th>Example</th>
<th>Complexity</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://blog.finxter.com/how-to-get-the-key-with-minimum-value-in-a-python-dictionary/" target="_blank" rel="noreferrer noopener">Index (Get)</a></td>
<td><code>dict[k]</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Store</a></td>
<td><code>dict[k] = v</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Length</a></td>
<td><code>len(dict)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Delete</a></td>
<td><code>del dict[key]</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Pop</a></td>
<td><code>dict.pop(k)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Clear</a></td>
<td><code>dict.clear()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Keys</a></td>
<td><code>dict.keys()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Construction</a></td>
<td><code>dict(...)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Iteration</a></td>
<td><code>for k in dict:</code></td>
<td><em>O(n)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>Most operations are O(1) because <a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Python dictionaries</a> share multiple properties of Python sets (such as fast membership operation).</p>
<h2>Composing Complexity Classes</h2>
<p>Now, you know the complexity of different operations. But how do you obtain the complexity of your algorithm? </p>
<p>The concept is simple: you break the big problem (<em>knowing the complexity of the whole algorithm</em>) into a series of smaller problems (<em>knowing the complexity of individual operations</em>). </p>
<p>Then, you recombine the individual operation’s complexities to obtain the solution to the big problem.</p>
<p>How? Let’s start with a small example: you first get a list from a <a href="https://blog.finxter.com/how-to-convert-a-list-of-list-to-a-dictionary-in-python/" target="_blank" rel="noreferrer noopener">dictionary of list</a> values. Then you sort the list:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">d = {1: [3, 1, 2, 4], 2: [4, 4, 1, 9]} lst = d.get(1)
lst.sort()
print(lst)
# [1, 2, 3, 4]</pre>
<p>Try it yourself in our interactive code shell (click “run” to execute the code):</p>
<p> <iframe src="https://repl.it/@finxter/complexity?lite=true" scrolling="no" allowtransparency="true" allowfullscreen="true" sandbox="allow-forms allow-pointer-lock allow-popups allow-same-origin allow-scripts allow-modals" width="100%" height="1100px" frameborder="no"></iframe> </p>
<p>You have four operations in the code snippet. Let’s annotate each operation with a complexity class.</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group=""># Operation 1: Dictionary Creation --> O(n)
d = {1: [3, 1, 2, 4], 2: [4, 4, 1, 9]} # Operation 2: Dictionary Get --> O(1)
lst = d.get(1) # Operation 3: List Sorting --> O(n log n)
lst.sort() # Operation 4: Print List --> O(n)
print(lst)</pre>
<p>Knowing the <a href="https://blog.finxter.com/runtime-complexity-of-python-list-methods-easy-table-lookup/" target="_blank" rel="noreferrer noopener">complexity </a>classes of the different operations, you can recombine it as follows:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">O(n) + O(1) + O(n log n) + O(n)
(1) = O(n + 1 + n log n + n)
(2) = O(n log n + 2n + 1)
(3) = O(n log n)</pre>
<p>You see in Equation <code>(1)</code> what you could call the <em><strong>“chain rule of complexity analysis”</strong></em>: <code>O(f(n)) + O(g(n)) = O(f(n) + g(n))</code>. </p>
<p>You can see in Equation <code>(3)</code> that the Big-O notation focuses only on the largest growing term. In our case, <code>O(n log n)</code> grows faster than <code>O(2n)</code>.</p>
<p>Here are two important examples of Big-O recombination:</p>
<ul>
<li><code>O(f(n)) + O(f(n)) = O(f(n) + f(n)) = O(2f(n)) = O(f(n)</code>. In other words, Executing an operation a constant (fixed) number of times, doesn’t change the overall complexity of the algorithm.</li>
<li><code>O(f(n) + g(n)) = O(f(n))</code> if the complexity function <code>f(n)</code> grows faster than <code>g(n)</code>. An example is <code>O(n³ + 1000n³) = O(n³)</code>. </li>
</ul>
<p> In programming, you can also have <strong>conditional execution</strong>: </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">if condition: f(n)
else: g(n)</pre>
<p>You can recombine the complexity class of the overall code snippet as follows: <code>O(max(f(n), g(n))</code>. Roughly speaking, (if the <a href="https://blog.finxter.com/how-to-conditionally-select-elements-in-a-numpy-array/" target="_blank" rel="noreferrer noopener">condition </a>can be true), the complexity of the conditional execution is the <a href="https://blog.finxter.com/integer-and-float-maximums-in-pythons-max-function/" target="_blank" rel="noreferrer noopener">maximum </a>of both blocks <code>f(n)</code> or <code>g(n)</code>. </p>
<p><strong>Example</strong>: </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">if lst: lst.sort()
else: lst = [1, 2, 3, 4]</pre>
<p>The complexity is <code>O(n log n)</code> because it grows faster than <code>O(n)</code> — the complexity of the block in the <a href="https://blog.finxter.com/if-then-else-in-one-line-python/" target="_blank" rel="noreferrer noopener">else statement</a>.</p>
<p>Another possibility is to repeatedly execute a certain function (e.g., in a <a href="https://blog.finxter.com/python-one-line-for-loop-a-simple-tutorial/" target="_blank" rel="noreferrer noopener">for loop</a>). </p>
<p>If you repeat function <code>f(n)</code> <code>m</code> times, the computational complexity is <code>m * O(f(n)) = O(m f(n))</code>. If <code>m</code> is a constant, the computational complexity simplifies to <code>O(f(n))</code>. </p>
<h2>Where to Go From Here?</h2>
<p>Enough theory, let’s get some practice!</p>
<p>To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?</p>
<p><strong>Practice projects is how you sharpen your saw in coding!</strong></p>
<p>Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?</p>
<p>Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.</p>
<p>Join my free webinar <a rel="noreferrer noopener" href="https://blog.finxter.com/webinar-freelancer/" target="_blank">“How to Build Your High-Income Skill Python”</a> and watch how I grew my coding business online and how you can, too—from the comfort of your own home.</p>
<p><a href="https://blog.finxter.com/webinar-freelancer/" target="_blank" rel="noreferrer noopener">Join the free webinar now!</a></p>
</div>
https://www.sickgaming.net/blog/2020/05/...perations/
<div><figure class="wp-block-embed-wordpress wp-block-embed is-type-video is-provider-youtube">
<div class="wp-block-embed__wrapper">
<div class="ast-oembed-container"><iframe title="Big-O Runtime Complexity List and Set Operations" width="1400" height="788" src="https://www.youtube.com/embed/SmutQEAp1w8?feature=oembed" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe></div>
</div>
</figure>
<p>In this tutorial, you’ll learn the runtime complexity of different Python operations. </p>
<p>Then, you’ll learn how to calculate the complexity of your own function by combining the complexity classes of its constituents. This is called <em>“static analysis”</em> </p>
<p>The tutorial is loosely based on (<a rel="noreferrer noopener" href="https://www.ics.uci.edu/~brgallar/week8_2.html" target="_blank">source</a>) but it extends it significantly with more practical examples, interactive snippets, and explanatory material.</p>
<h2>Introducing Big-O</h2>
<p><strong>Definition</strong>: The complexity of an operation (or an algorithm for that matter) is the number of resources that are needed to run it (<a rel="noreferrer noopener" href="https://en.wikipedia.org/wiki/Computational_complexity" target="_blank">source</a>). Resources can be time (<em>runtime complexity</em>) or space (<em>memory complexity</em>). </p>
<p>So, how can you measure the complexity of an algorithm? In most cases, the complexity of an algorithm is not static. It varies with the size of the input to the algorithm or the operation. </p>
<p>For example, the <a rel="noreferrer noopener" href="https://blog.finxter.com/python-list-sort/" target="_blank">list method <code>list.sort()</code></a> has one input argument: the list object to be sorted. The runtime complexity is not constant, it increases with increasing size of the list. If there are more elements to be sorted, the runtime of the algorithm increases. </p>
<h3>Complexity Function</h3>
<p>Given input size <em><code>n</code></em>, you can describe the complexity of your algorithm with a function of the input <code><em>n</em> → <em>f</em>(<em>n</em>)</code> that defines the number of “resource units” (e.g., time, memory) needed to finish it (worst-case or average-case). </p>
<p>Say, you’ve got three implementations to <a rel="noreferrer noopener" href="https://blog.finxter.com/how-to-sort-a-list-alphabetically-in-python/" target="_blank">sort a list</a>: <code>implementation_1</code>, <code>implementation_2</code>, <code>implementation_3</code>. </p>
<figure class="wp-block-image size-large"><img src="https://blog.finxter.com/wp-content/uploads/2020/05/image-63.png" alt="" class="wp-image-8717" srcset="https://blog.finxter.com/wp-content/uploads/2020/05/image-63.png 736w, https://blog.finxter.com/wp-content/uplo...00x226.png 300w" sizes="(max-width: 736px) 100vw, 736px" /></figure>
<p>The figure shows the three complexity functions. The x axis measures the input size (in our example, it would be the list size). The y axis measures the complexity with respect to this input.</p>
<ul>
<li><code>implementation_1</code> has a quadratic complexity function <em>f(n) = n²</em>. </li>
<li><code>implementation_2</code> has a quadratic complexity function <em>f(n) = 2n²</em>.</li>
<li><code>implementation_3</code> has a logarithmic complexity function <em>f(n) = n log(n)</em>.</li>
</ul>
<p>You can see the code we used to generate this plot here:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">import matplotlib.pyplot as plt
import math implementation_1 = [n**2 for n in range(1, 100, 10)]
implementation_2 = [2*n**2 for n in range(1, 100, 10)]
implementation_3 = [n*math.log(n) for n in range(1, 100, 10)] plt.plot(implementation_1, '--.', label='implementation 1')
plt.plot(implementation_2, '-o', label='implementation 2')
plt.plot(implementation_3, '-x', label='implementation 3') plt.legend()
plt.xlabel('Input (ex: List Size)')
plt.ylabel('Complexity (ex: Runtime)')
plt.grid()
plt.show()</pre>
<p>Of course, it’s good to waste as little resources as possible so the logarithmic complexity function is superior to the quadratic complexity functions.</p>
<h3>Big-O Notation</h3>
<p>For large inputs, the runtime behavior will be dominated by the part of the complexity function that grows fastest. For example, a quadratic runtime complexity function <em>f(n) = 1000n² + 100000n + 999</em> will be much better than a cubic runtime complexity function <em>g(n) = 0.1n³</em>. </p>
<p>Why? Because sooner or later the function <em>g(n)</em> will produce much higher values than <em>f(n)</em> as the input size n increases.</p>
<p>In fact, you can argue that the only important part of a complexity function is the part that grows fastest with increasing input size.</p>
<p>This is exactly what’s the Big-O notation is all about:</p>
<p><strong><em>The </em></strong><em><strong>Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.</strong></em> (<a rel="noreferrer noopener" href="https://en.wikipedia.org/wiki/Big_O_notation" target="_blank">wiki</a>)</p>
<p>Roughly speaking, you remove everything but the fastest-growing term from the complexity function. This allows you to quickly compare different algorithms against each other.</p>
<p>To show this, have a look at our two examples:</p>
<ul>
<li>Complexity function <em>f(n) = 1000n² + 100000n + 999</em> grows like <em>O(n²)</em>.</li>
<li>Complexity function <em>g(n) = 0.1n³</em> grows like <em>O(n³)</em>. </li>
</ul>
<p>By reducing the complexity function to its asymptotic growth, you can immediately see that the former is superior to the latter in terms of runtime complexity—without being distracted by all the constant factors in front of the constituents or the constituents with smaller asymptotic growth.</p>
<h3>Examples Big-O of Complexity Functions</h3>
<p>So, here are a few examples of complexity functions and their asymptotic growth in Big-O notation:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Complexity Function</th>
<th>Asymptotic Growth</th>
</tr>
</thead>
<tbody>
<tr>
<td><em>f(n) = 10000</em></td>
<td><em>O(<em>1</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = n + 1000000</em></td>
<td><em>O(<em>n</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = 33n + log(n)</em></td>
<td><em>O(<em>n</em> log(n))</em></td>
</tr>
<tr>
<td><em>f(n) = 33n + 4n * log(n)</em></td>
<td><em>O(<em>n</em> log(n))</em></td>
</tr>
<tr>
<td><em>f(n) = n² + n</em></td>
<td><em>O(<em>n²</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = 1000n² + 100000n + 999</em></td>
<td><em>O(<em>n²</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = 0.000000001n³ + 4n² + 100000n + 999</em></td>
<td><em>O(<em>n³</em>)</em></td>
</tr>
<tr>
<td><em>f(n) = n * n³ + 33n</em></td>
<td><em>O(<em>n³</em>)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>You can see that the asymptotic growth of a function (in Big-O notation) is dominated by the fastest-growing term in the function equation.</p>
<h2>Python Complexity of Operations</h2>
<p>Let’s explore the complexity of Python operations—classified by the data structure on which you perform those operations. A great coder will always use the data structure that suits their needs best. </p>
<p>In general, the list data structure supports more operations than the set data structure as it keeps information about the ordering of the elements—at the cost of higher computational complexity.</p>
<h3>Python List Complexity</h3>
<p>Assume that the length of the data type is defined as <code>n</code> (that is—<code>n = len(data_type)</code>). You can now categorize the asymptotic complexity of the different complexity functions as follows:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Operation</th>
<th>Example</th>
<th>Complexity</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://blog.finxter.com/python-list-index/" target="_blank" rel="noreferrer noopener">Index</a></td>
<td><code>l[i]</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/resolve-indexerror-list-assignment-index-out-of-range/" target="_blank" rel="noreferrer noopener">Store</a></td>
<td><code>l[i] = 42</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-length-whats-the-runtime-complexity-of-len/" target="_blank" rel="noreferrer noopener">Length</a></td>
<td><code>len(l)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-append/" target="_blank" rel="noreferrer noopener">Append</a></td>
<td><code>l.append(42)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-pop/" target="_blank" rel="noreferrer noopener">Pop</a></td>
<td><code>l.pop()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-clear/" target="_blank" rel="noreferrer noopener">Clear</a></td>
<td><code>l.clear()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a rel="noreferrer noopener" href="https://blog.finxter.com/introduction-to-slicing-in-python/" target="_blank">Slicin</a><a href="https://blog.finxter.com/introduction-to-slicing-in-python/" target="_blank" rel="noreferrer noopener">g</a></td>
<td><code>l[a:b]</code></td>
<td><em>O(b-a)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-extend/" target="_blank" rel="noreferrer noopener">Extend</a></td>
<td><code>l1.extend(l2)</code></td>
<td><em>O(len(l1)+len(l2))</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">Constructor</a></td>
<td><code>list(iter)</code></td>
<td><em>O(len(iter))</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-string-contains/" target="_blank" rel="noreferrer noopener">Equality</a></td>
<td><code>l1 == l2</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-slice-assignment/" target="_blank" rel="noreferrer noopener">Slice Assign</a></td>
<td><code>l[a:b] = ...</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-remove/" target="_blank" rel="noreferrer noopener">Delete</a></td>
<td><code>del l[i]</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-remove/" target="_blank" rel="noreferrer noopener">Remove</a></td>
<td><code>l.remove(...)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">Membership</a></td>
<td><code>x in l</code> / <code>x not in l</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-copy/" target="_blank" rel="noreferrer noopener">Copy</a></td>
<td><code>l.copy()</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-pop/" target="_blank" rel="noreferrer noopener">Pop</a></td>
<td><code>l.pop(0)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/how-to-find-the-minimum-of-a-list-of-lists-in-python/" target="_blank" rel="noreferrer noopener">Min</a></td>
<td><code>min(l)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/how-to-find-the-max-of-list-of-lists-in-python/" target="_blank" rel="noreferrer noopener">Max</a></td>
<td><code>max(l)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-reverse/" target="_blank" rel="noreferrer noopener">Reverse</a></td>
<td><code>l.reverse()</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-loops/" target="_blank" rel="noreferrer noopener">Iterate</a></td>
<td><code>for x in l:</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-sort/" target="_blank" rel="noreferrer noopener">Sort</a></td>
<td><code>l.sort()</code></td>
<td><em>O(n log(n))</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-list-concatenation-add-vs-inplace-add-vs-extend/" target="_blank" rel="noreferrer noopener">Multiply</a></td>
<td><code>l*k</code></td>
<td><em>O(n k)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>Tuples are similar as lists—with a few exceptions: you cannot modify a tuple because they are immutable. </p>
<p>Let’s consider another important data structure:</p>
<h3>Python Set Complexity</h3>
<p>Assume that the length of the data type is defined as <code>n</code> (that is—<code>n = len(data_type)</code>). If there are two sets in a single operation such as <code>s1 == s2</code>, the lengths are given by the variables <code>n1</code> and <code>n2</code>. You can now categorize the asymptotic complexity of the different complexity functions as follows:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Operation</th>
<th>Example</th>
<th>Complexity</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Length</a></td>
<td><code>len(s)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Add</a></td>
<td><code>s.add(42)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><strong><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Membership</a></strong></td>
<td><strong><code>42 in s</code> / <code>42 not in s</code></strong></td>
<td><strong><em>O(1)</em></strong></td>
</tr>
<tr>
<td><strong><a href="https://blog.finxter.com/sets-in-python/" target="_blank" rel="noreferrer noopener">Remove</a></strong></td>
<td><strong><code>s.remove(42)</code></strong></td>
<td><strong><em>O(1)</em></strong></td>
</tr>
<tr>
<td>Pop</td>
<td><code>s.pop()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td>Clear</td>
<td><code>s.clear()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td>Constructor</td>
<td><code>set(iter)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td>Equality</td>
<td><code>s1 == s2</code> / <code>s1 != s2</code></td>
<td><em>O(min(n1, n2))</em></td>
</tr>
<tr>
<td>Union</td>
<td><code>s1 | s2</code></td>
<td><em>O(n1+n2)</em></td>
</tr>
<tr>
<td>Intersection</td>
<td><code>s1 & s2</code></td>
<td><em>O(min(n1, n2))</em></td>
</tr>
<tr>
<td>Difference</td>
<td><code>s1 - s2</code></td>
<td><em>O(n2)</em></td>
</tr>
<tr>
<td>Symmetric Difference</td>
<td><code>s1 ^ s2</code></td>
<td><em>O(n1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-loops/" target="_blank" rel="noreferrer noopener">Iteration</a></td>
<td><code>for x in s:</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td>Copy</td>
<td><code>s.copy()</code></td>
<td><em>O(n)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>I highlighted the set operations that are more efficient than the corresponding list operations. The reason for those being O(1) rather than O(n) is that the <a href="https://blog.finxter.com/python-lists/" target="_blank" rel="noreferrer noopener">list data structure</a> also maintains the ordering of the elements—which incurs additional overhead.</p>
<h3>Python Dictionary Complexity</h3>
<p>Now, have a look at the time complexity of Python dictionary operations:</p>
<figure class="wp-block-table is-style-stripes">
<table>
<thead>
<tr>
<th>Operation</th>
<th>Example</th>
<th>Complexity</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://blog.finxter.com/how-to-get-the-key-with-minimum-value-in-a-python-dictionary/" target="_blank" rel="noreferrer noopener">Index (Get)</a></td>
<td><code>dict[k]</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Store</a></td>
<td><code>dict[k] = v</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Length</a></td>
<td><code>len(dict)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Delete</a></td>
<td><code>del dict[key]</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Pop</a></td>
<td><code>dict.pop(k)</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Clear</a></td>
<td><code>dict.clear()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Keys</a></td>
<td><code>dict.keys()</code></td>
<td><em>O(1)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Construction</a></td>
<td><code>dict(...)</code></td>
<td><em>O(n)</em></td>
</tr>
<tr>
<td><a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Iteration</a></td>
<td><code>for k in dict:</code></td>
<td><em>O(n)</em></td>
</tr>
</tbody>
</table>
</figure>
<p>Most operations are O(1) because <a href="https://blog.finxter.com/python-dictionary/" target="_blank" rel="noreferrer noopener">Python dictionaries</a> share multiple properties of Python sets (such as fast membership operation).</p>
<h2>Composing Complexity Classes</h2>
<p>Now, you know the complexity of different operations. But how do you obtain the complexity of your algorithm? </p>
<p>The concept is simple: you break the big problem (<em>knowing the complexity of the whole algorithm</em>) into a series of smaller problems (<em>knowing the complexity of individual operations</em>). </p>
<p>Then, you recombine the individual operation’s complexities to obtain the solution to the big problem.</p>
<p>How? Let’s start with a small example: you first get a list from a <a href="https://blog.finxter.com/how-to-convert-a-list-of-list-to-a-dictionary-in-python/" target="_blank" rel="noreferrer noopener">dictionary of list</a> values. Then you sort the list:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">d = {1: [3, 1, 2, 4], 2: [4, 4, 1, 9]} lst = d.get(1)
lst.sort()
print(lst)
# [1, 2, 3, 4]</pre>
<p>Try it yourself in our interactive code shell (click “run” to execute the code):</p>
<p> <iframe src="https://repl.it/@finxter/complexity?lite=true" scrolling="no" allowtransparency="true" allowfullscreen="true" sandbox="allow-forms allow-pointer-lock allow-popups allow-same-origin allow-scripts allow-modals" width="100%" height="1100px" frameborder="no"></iframe> </p>
<p>You have four operations in the code snippet. Let’s annotate each operation with a complexity class.</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group=""># Operation 1: Dictionary Creation --> O(n)
d = {1: [3, 1, 2, 4], 2: [4, 4, 1, 9]} # Operation 2: Dictionary Get --> O(1)
lst = d.get(1) # Operation 3: List Sorting --> O(n log n)
lst.sort() # Operation 4: Print List --> O(n)
print(lst)</pre>
<p>Knowing the <a href="https://blog.finxter.com/runtime-complexity-of-python-list-methods-easy-table-lookup/" target="_blank" rel="noreferrer noopener">complexity </a>classes of the different operations, you can recombine it as follows:</p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">O(n) + O(1) + O(n log n) + O(n)
(1) = O(n + 1 + n log n + n)
(2) = O(n log n + 2n + 1)
(3) = O(n log n)</pre>
<p>You see in Equation <code>(1)</code> what you could call the <em><strong>“chain rule of complexity analysis”</strong></em>: <code>O(f(n)) + O(g(n)) = O(f(n) + g(n))</code>. </p>
<p>You can see in Equation <code>(3)</code> that the Big-O notation focuses only on the largest growing term. In our case, <code>O(n log n)</code> grows faster than <code>O(2n)</code>.</p>
<p>Here are two important examples of Big-O recombination:</p>
<ul>
<li><code>O(f(n)) + O(f(n)) = O(f(n) + f(n)) = O(2f(n)) = O(f(n)</code>. In other words, Executing an operation a constant (fixed) number of times, doesn’t change the overall complexity of the algorithm.</li>
<li><code>O(f(n) + g(n)) = O(f(n))</code> if the complexity function <code>f(n)</code> grows faster than <code>g(n)</code>. An example is <code>O(n³ + 1000n³) = O(n³)</code>. </li>
</ul>
<p> In programming, you can also have <strong>conditional execution</strong>: </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">if condition: f(n)
else: g(n)</pre>
<p>You can recombine the complexity class of the overall code snippet as follows: <code>O(max(f(n), g(n))</code>. Roughly speaking, (if the <a href="https://blog.finxter.com/how-to-conditionally-select-elements-in-a-numpy-array/" target="_blank" rel="noreferrer noopener">condition </a>can be true), the complexity of the conditional execution is the <a href="https://blog.finxter.com/integer-and-float-maximums-in-pythons-max-function/" target="_blank" rel="noreferrer noopener">maximum </a>of both blocks <code>f(n)</code> or <code>g(n)</code>. </p>
<p><strong>Example</strong>: </p>
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">if lst: lst.sort()
else: lst = [1, 2, 3, 4]</pre>
<p>The complexity is <code>O(n log n)</code> because it grows faster than <code>O(n)</code> — the complexity of the block in the <a href="https://blog.finxter.com/if-then-else-in-one-line-python/" target="_blank" rel="noreferrer noopener">else statement</a>.</p>
<p>Another possibility is to repeatedly execute a certain function (e.g., in a <a href="https://blog.finxter.com/python-one-line-for-loop-a-simple-tutorial/" target="_blank" rel="noreferrer noopener">for loop</a>). </p>
<p>If you repeat function <code>f(n)</code> <code>m</code> times, the computational complexity is <code>m * O(f(n)) = O(m f(n))</code>. If <code>m</code> is a constant, the computational complexity simplifies to <code>O(f(n))</code>. </p>
<h2>Where to Go From Here?</h2>
<p>Enough theory, let’s get some practice!</p>
<p>To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?</p>
<p><strong>Practice projects is how you sharpen your saw in coding!</strong></p>
<p>Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?</p>
<p>Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.</p>
<p>Join my free webinar <a rel="noreferrer noopener" href="https://blog.finxter.com/webinar-freelancer/" target="_blank">“How to Build Your High-Income Skill Python”</a> and watch how I grew my coding business online and how you can, too—from the comfort of your own home.</p>
<p><a href="https://blog.finxter.com/webinar-freelancer/" target="_blank" rel="noreferrer noopener">Join the free webinar now!</a></p>
</div>
https://www.sickgaming.net/blog/2020/05/...perations/