Different algorithms achieve the same goal in different ways. Linear search and binary search do the same thing in different ways. The various sorts do the same thing in different ways.

Mathematically, they are equivalent, as they are functions with the same behaviour. But computationally, they are very different.

Two trains are on the same track a distance \(100\text{ km}\) apart, heading towards one another each a speed of \(50\text{ km}\cdot\text{h}^{-1}\). A fly, staritng out at the front of one train, flies towards the other at a speed of \(75\text{km}\cdot\text{h}^{-1}\). Upon reaching the other train, the fly turns around and continues towards the first train. How many kilometers does the fly travel before being squashed in the collision of the two trains?

— the Two Trains Puzzle

You can solve this in many ways. The simple, brute-force method is as follows:

Let \(t\) be the time elapsed. The fly reaches the second train when^[1]

\[75t=100-50t\]

or \(t_1=\frac{4}{5}\text{ h}\), at which point it has traveled a distance of \(d_1=75\text{ km}\). It proceeds to turn around and reaches the first train again when

\[60-75t=40+50t\]

or \(t_2=\frac{4}{25}\text{ h}\). Continuing, we will obtain the series

\[75\sum_{n=1}^{\infty}\frac{4}{5^n}\]

which converges to \(75\text{ km}\).

Alternatively, we can note that the fly will be flying until the to trains meet, which they will do one hour into the scenario. As such, the fly will cover \(75\text{ km}\).

Both solutions are equally valid. They’re mathematically equivalent.

But clearly, the second option is superior when it comes to computation. Why come up with, and evaluate, an infinite series if you could come up with the solution that only requires two simple multiplications?

Writing faster algorithms — and optimization in general — is really about being able to find and exploit mathematically equivalent processes that aren’t computationally equivalent.

There’s no really good way to train this other than to practice and to overthink problems; but for now, try optimizing the following code snippets:

<span id="L1" class="line"><span class="k">if</span> <span class="p">(</span><span class="n">grade</span> <span class="o">&gt;</span> <span class="mi">100</span> <span class="o">||</span> <span class="n">grade</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span></span>
<span id="L2" class="line">    <span class="k">return</span> <span class="s">"X"</span><span class="p">;</span></span>
<span id="L3" class="line"><span class="k">if</span> <span class="p">(</span><span class="n">grade</span> <span class="o">&gt;=</span> <span class="mi">80</span> <span class="o">&amp;&amp;</span> <span class="n">grade</span> <span class="o">&lt;=</span> <span class="mi">100</span><span class="p">)</span></span>
<span id="L4" class="line">    <span class="k">return</span> <span class="s">"A"</span><span class="p">;</span></span>
<span id="L5" class="line"><span class="k">if</span> <span class="p">(</span><span class="n">grade</span> <span class="o">&gt;=</span> <span class="mi">70</span> <span class="o">&amp;&amp;</span> <span class="n">grade</span> <span class="o">&lt;</span> <span class="mi">80</span><span class="p">)</span></span>
<span id="L6" class="line">    <span class="k">return</span> <span class="s">"B"</span><span class="p">;</span></span>
<span id="L7" class="line"><span class="k">if</span> <span class="p">(</span><span class="n">grade</span> <span class="o">&gt;=</span> <span class="mi">60</span> <span class="o">&amp;&amp;</span> <span class="n">grade</span> <span class="o">&lt;</span> <span class="mi">70</span><span class="p">)</span></span>
<span id="L8" class="line">    <span class="k">return</span> <span class="s">"C"</span><span class="p">;</span></span>
<span id="L9" class="line"><span class="k">if</span> <span class="p">(</span><span class="n">grade</span> <span class="o">&gt;=</span> <span class="mi">50</span> <span class="o">&amp;&amp;</span> <span class="n">grade</span> <span class="o">&lt;</span> <span class="mi">60</span><span class="p">)</span></span>
<span id="L10" class="line">    <span class="k">return</span> <span class="s">"D"</span><span class="p">;</span></span>
<span id="L11" class="line"><span class="k">if</span> <span class="p">(</span><span class="n">grade</span> <span class="o">&gt;=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">grade</span> <span class="o">&lt;</span> <span class="mi">50</span><span class="p">)</span></span>
<span id="L12" class="line">    <span class="k">return</span> <span class="s">"F"</span><span class="p">;</span></span>

<span id="L1" class="line"><span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span></span>
<span id="L2" class="line">    <span class="k">for</span> <span class="p">(</span><span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">j</span><span class="p">)</span></span>
<span id="L3" class="line">        <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">&lt;=</span> <span class="n">j</span><span class="p">)</span></span>
<span id="L4" class="line">            <span class="n">sum</span> <span class="o">+=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span></span>

---

1. left side is location of the fly from its initial point at time \(t\); right side is location of the second train from the fly’se inital point at time \(t\)