CODEWITHSUNDEEP
sortinglanguage-agnostictime-complexitybig-ocomputer-science
luke
luke

Reputation: 17

Time complexity of sorting two arrays

If I have two unsorted arrays of different sizes and I want to sort them both, I get that the runtime complexity will be O(n log(n)), but what does the n represent? The larger or smaller array?

Upvotes: 0

Views: 1243

Answers (2)

Asker
Asker

Reputation: 1685

n represents the size of the larger array.

First, recall what Big-O means: a function k is O(n log(n)) if and only if there is some constant M such that k(n) < M * n log(n) for all n larger than some size.

Now, what is the function k in this case? It is the runtime of a program which sorts both arrays. Rephrasing the above definition of Big-O in this way, we see that the statement "The time complexity is O(n log(n))" is equivalent to the sentence

"The runtime given size n is no more than a constant multiple of (n log n)."

So we are trying to bound the size of the runtime based on n. What is n?

Well, n can't be the size of the smaller array, since the size of the smaller array does not put an upper bound on the size of the larger array, on which the runtime depends. That is, even if we know that the smaller array's size is tiny (say, 1 element), that does not stop the larger array's size from being huge (say, 995,566,214,678 elements), and therefore the smaller array's size alone cannot put an upper limit on the total runtime.

Now, what if we let n be the size of the larger array -- would that solve our problem?

In a word, yes.

This is because the size of the smaller array is less than that of the larger array, so the size of the larger array does bound the size of the smaller array, and thus it also bounds the total runtime.

Upvotes: 0

akuzminykh
akuzminykh

Reputation: 4723

In O-notation the variable n represents the "size" of the problem. E.g., if you have a list of 10 elements and want to sort it, the size of the problem is 10. With two arrays we have two problem sizes, n and m. Therefore the complexity is O(nlog(n)) + O(mlog(m)), which is the same as O(nlog(n) + mlog(m)).

Upvotes: 1

Related Questions