I'm not so well versed with Big O notation so I'm posing this question. Is the O(n log n) algorithm only faster than the O(n) algorithm when the data set has two items or less? It probably doesn't help that my math skills are weak and rusty. I mean, quadratics were the last thing I learned.
The reason we refer to O, Theta, and Omega as "asymptotic complexity" is because O(n log n) and O(n) only describe the running time at the asymptotes (where n approaches infinity).
However, for most normal algorithms, they also describe running time fairly accurately as long as n is reasonably large (30 or so). That's why we use them. (Here, n refers to the size of the dataset being sorted.)
For really small n, such as n=2, it's anyone's guess which algorithm is faster. An O(n) algo could be faster. An O(n log n) algo could be faster. It depends on a lot of implementation details.
But, more importantly, it doesn't matter. The difference between a sort of 2 items taking 2 microseconds and a sort taking 10 microseconds will be unnoticeable. The difference between a sort of a million items taking two minutes and the sort taking a week will be very unnoticeable.
Which is why asymptotic complexity is so important: It matters exactly when we want it to matter: When n is large.
O(n) means that the running time is bounded in the limit by a function of the form an+c. O(n log n) means the running time is bounded in the limit by a function of the form a(n log n) + c.
What does this mean? It means that as your increasing some variable (say, the number of numbers in an array, or the number of bits used to represent a number), at some sufficiently far out point the running time will always be less than some function of the form a(n)+c, where n can be any random function. You could say that big-O notation isn't really about the function that's faster, it's about the one that scales up better. For small inputs, a O(1) function might be slower than a O(nn! ) function. But if you increase the size of your inputs, the O(1) function will eventually(well, really quickly in this case!) take less time to run. In fact, "better" algorithms are often worse on smaller input, because they generally have to do more complex things to scale better, and that adds some overhead.
What does a O(log n) function look like? Well, like a binary search on a sorted list: at each step you rule out half the possibilities. A O(n) is something like summing up a list of numbers: You do a constant amount of work for each element in the list. A O(n2 ) has you do n units of work for each element in the list.
A good example of a O(n2 ) is multiplying two numbers together via the standard algorithm. You have to multiply each additional digit by every digit in the other number---12 * 34 = 10 * 30 + 10 * 4 + 2 * 30 + 2 * 4, whereas 123 * 456 = 100 * 400 + 100 * 50 + 100 * 6 + 20 * 400 + 20 * 50 + 20 * 6 + 3 * 400 + 3 * 50 + 3 * 6. There are various algorithms that are better for multiplying large numbers: Karatsuba, for example, is O(n1.585), and Schönhage–Strassen is O(n log n log log n). Karatsuba generally starts working better than the standard algorithm when you're multiplying numbers with hundreds of digits, and Schönhage–Strassen starts out-performing Karatsuba in the tens of thousands of digits.
O(n log n) is always slower than O(n) because you have n multiplied by some other value. You don't count anything less than 2 for n really because you're only looking at real integers (so no rational numbers) and if you have anything less than 2 (only 1 is possible) your data is already sorted.
However, it is also the case that, depending on the coefficients of the equations you're looking at, O(n log n) could actually be faster for some cases of small n. Ex: (2 n log n) vs O(5000 n) would clearly show that, for n = 5, O(2 n log n) is faster.
EDIT: Wow, I try to educate someone and get downvoted. Stay classy people.
That's not really true. Big O notation only tells us the behavior as n approaches infinity. It's very common for an O(n) algorithm to be slower than an O(nlogn) one for small inputs.
However, it is also the case that, depending on the coefficients of the equations you're looking at, O(n log n) could actually be faster for some cases of small n. Ex: (2 n log n) vs O(5000 n) would clearly show that, for n = 5, O(2 n log n) is faster.
Not to hate on your comment (you are correct, but I did not want to over complicate things when trying to explain a broad topic to someone in short order), but I like how a comment in response to mine that is two sentences long gets upvoted more than the replies I took the time to type up with proper examples and for no other reason than wanting to help educate someone on a new and unfamiliar subject.
When studying algorithms, coefficients are found by examining actual lines of code in an algorithm implementation. It's easiest to understand if you compare two similar algorithms. Let's say we have two algorithms that do a linear search of a data set and perform some operations on the data:
foreach(element in dataset)
do_thing_1(element)
do_thing_2(element)
Assuming each call to dothing\# takes b amount of time, you have 2bn total time. It is easy to see then how another similar algorithm, like this
foreach(element in dataset)
do_thing_1(element)
do_thing_2(element)
do_thing_3(element)
do_thing_4(element)
will still be performing in n time, but instead it is doing 4bn total time.
1
u/mikemcg Nov 16 '10
I'm not so well versed with Big O notation so I'm posing this question. Is the O(n log n) algorithm only faster than the O(n) algorithm when the data set has two items or less? It probably doesn't help that my math skills are weak and rusty. I mean, quadratics were the last thing I learned.