0

Finding intersection of two arrays can be done if you sort the 2 arrays and then do a linear step through to record the common elements. This would take O(nlogn) + O(nlogn) + O(n)

Alternatively, you could compare each element in the first array with each element in the second array and you would get a O(n^2) run-time complexity.

How can I prove the first approach is better than the second?

Improve this question
11
  • 4
    Because the limit of n log n / n^2 as n approaches infinity is 0, which means n log n is smaller for big enough values of n. Is this what you're looking for? Commented Apr 26, 2011 at 19:37
  • 2
    As far as I am concerned, you just did. You just need to write it up formally. Commented Apr 26, 2011 at 19:38
  • so even if we add the three terms together O(nlogn) + O(nlogn) + O(n) .. it is always going to be smaller than O(n^2) ? Commented Apr 26, 2011 at 19:38
  • The first approach is not necessarily better for all inputs. Only if you know the actual constants hidden by the O() notation can you find the "cutoff" point (or at least an approximation to it) where the asymptotically better algorithm should start "winning". Commented Apr 26, 2011 at 19:40
  • @Pan: Yes, because there will always be values of c1, c2 and n for which c1 * n * lg(n) < c2 * n^2 Commented Apr 26, 2011 at 19:40

3 Answers 3

Reset to default
2

First of all, O(nlogn) + O(nlogn) + O(n) doesn't make much sense, since O(f) is a set, not a number.

What you mean is O(nlogn + nlogn + n), which can be shown to be equal to O(nlogn). Just look at what it means for a function f to belong to the set O(g):

f is an element of O(g) iff there exists c>0 and x0 such that for all x>x0:
|f(x)| <= c*|g(x)|

By setting f=nlogn and g=nlogn+nlogn+n, it follows that f is in O(g), and hence that O(nlogn) == O(nlogn + nlogn + n).

Improve this answer
Sign up to request clarification or add additional context in comments.

18 Comments

I've seen Big-O used on the left hand side of an equation, for example in CLRS. It's essentially used to indicate "any function in the set".
@abeln: can you give a more specific reference? CLRS chapter/paragraph would be helpful. If you happen to have the 2nd edition paperback, the page number will suffice.
@Philip: I don't have it with me right now. Now that I check, the Wikipedia page also mentions that use. en.wikipedia.org/wiki/Big_O_notation
@abeln: interesting, it even discusses the issue at hand: "it would be more precise to use set notation [...] however, the use of the equals sign is customary". Being German, I prefer using correct notation over a customary wrong one, though.
@Philip: You can make it as cumbersome (an so unreadable) as you like :-) Most mathematics textbooks use that notation. There is no issue of correctness, it is just convenient notation. As long as the meaning is clear, it is correct and very convenient notation. I suggest you look at some of the threads on math.stackexchange which use this notation. ANd, that is the sum of reciprocals of primes upto some number which is asymptotically log log x (which proves the divergence of the sum of reciprocals of primes and so there are infinite primes). This is a well known result in number theory.
|
0

It's important to remember that Big-O notation is the "worst case" run-time meaning that you are iterating over an array that is crushingly large.

O(N) + O(N) is equivalent to O(2N) which is equivalent to O(N)

Thus, O(nlogn) + O(nlogn) + O(n) is merely O(nlogn)

O(nlogn) < O(n^2)

Improve this answer

2 Comments

@abeln What could be improved about my response given the context?
You could add that the comparison: O(nlogn) < O(n^2) reduces to O(logn) < O(n) after factoring-out an 'n'.
0

O(nlogn) + O(nlogn) + O(n) = O(nlogn)

O(nlogn) < c*nlogn

O(n^2) < d*(n^2)

c*nlogn < d*(n^2)

logn < d/c*n

You can prove in many ways that there's an N where logn < d/c*n is always true.

You could even draw it.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.