Is an algorithm with a worst-case time complexity of O(n) always faster than an algorithm with a worst-case time complexity of O(n^2)?
<p>This question has appeared in my algorithms class. Here's my thought:</p>

<p>I think the answer is <em>no</em>, an algorithm with worst-case time complexity of O(n) is not <em>always</em> faster than an algorithm with worst-case time complexity of O(n^2).</p>

<p>For example, suppose we have total-time functions S(n) = 99999999n and T(n) = n^2. Then clearly S(n) = O(n) and T(n) = O(n^2), but T(n) is faster than S(n) for all n &lt; 99999999.</p>

<p>Is this reasoning valid? I'm slightly skeptical that, while this is a counterexample, it might be a counterexample to the wrong idea.</p>

<p>Thanks so much!</p>