StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It is <code>O(n²)</code> where n = max(length(s1),length(s2)) (which can be determined in less than quadratic time - see below). Let's take a look at a textbook definition:</p> <blockquote> <p>f(n) ∈ O(g(n)) if a positive real number c and positive integer N exist such that f(n) <= c g(n) for all n >= N</p> </blockquote> <p>By this definition we see that n represents a number - in this case that number is the length of the string passed in. However, there is an apparent discrepancy, since this definition provides only for a single variable function <code>f(n)</code> and here we clearly pass in 2 strings with independent lengths. So we search for a multivariable definition for Big O. However, as demonstrated by Howell in <a href="http://www.google.com/url?sa=t&source=web&cd=3&ved=0CCUQFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.110.3078%26rep%3Drep1%26type%3Dpdf&rct=j&q=big%20o%20multivariable&ei=NtD6Tbn6Fa-v0AHBrOmsAw&usg=AFQjCNHO5zhRuDDD4nEdyHByAodgOU-xcg&cad=rja" rel="nofollow noreferrer">"On Asymptotic Notation with Multiple Variables"</a>:</p> <blockquote> <p>"it is impossible to define big-O notation for multi-variable functions in a way that implies all of these [commonly-assumed] properties."</p> </blockquote> <p>There is actually a formal definition for <a href="http://en.wikipedia.org/wiki/Big_O_notation#Multiple_variables" rel="nofollow noreferrer">Big O with multiple variables</a> however this requires extra constraints beyond single variable Big O be met, and is beyond the scope of most (if not all) algorithms courses. For typical algorithm analysis we can effectively reduce our function to a single variable by bounding all variables to a limiting variable <code>n</code>. In this case the variables (specifically, length(s1) and length(s2)) are clearly independent, but it is possible to bound them:</p> <p><strong>Method 1</strong></p> <pre><code>Let x1 = length(s1) Let x2 = length(s2) </code></pre> <p>The worst case scenario for this function occurs when there are no matches, therefore we perform x1 * x2 iterations.</p> <p>Because multiplication is commutative, the worst case scenario foo(s1,s2) == the worst case scenario of foo(s2,s1). We can therefore assume, without loss of generality, that x1 >= x2. (This is because, if x1 < x2 we could get the same result by passing the arguments in the reverse order).</p> <p><strong>Method 2</strong> (in case you don't like the first method)</p> <p>For the worst case scenario (in which s1 and s2 contain no common characters), we can determine length(s1) and length(s2) prior to iterating through the loops (in .NET and Java, determining the length of a string is O(1) - but in this case it is O(n)), assigning the greater to x1 and the lesser to x2. Here it is clear that x1 >= x2.</p> <p>For this scenario, we will see that the extra calculations to determine x1 and x2 make this O(n² + 2n) We use the following simplification rule <a href="http://en.wikipedia.org/wiki/Big_O_notation#Example" rel="nofollow noreferrer">which can be found here</a> to simplify to O(n²):</p> <blockquote> <p>If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.</p> </blockquote> <p><strong>Conclusion</strong></p> <p>for <code>n = x1</code> (our limiting variable), such that <code>x1 >= x2</code>, the worst case scenario is <code>x1 = x2</code>. Therefore: <code>f(x1) ∈ O(n²)</code></p> <p><strong>Extra Hint</strong></p> <p>For all <a href="https://stackoverflow.com/questions/tagged/homework+big-o">homework problems posted to SO related to Big O notation</a>, if the answer is not one of:</p> <pre><code>O(1) O(log log n) O(log n) O(n^c), 0<c<1 O(n) O(n log n) = O(log n!) O(n^2) O(n^c) O(c^n) O(n!) </code></pre> <p>Then the question is <em>probably</em> better off being posted to <a href="https://math.stackexchange.com/">https://math.stackexchange.com/</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload