Complexity analysis question

O, Ω and Θ complexity measurements all drop the constant multiplication factor, so none represent accurately what you mention.

No measurement of complexity that I know of is able to represent this (aside from counting the exact number of operations), because the exact complexity of an algorithm depends on its implementation (which is subject to software and programming language limitations) and is seldom a clean multiple of the complexity of another algorithm. So, such a measurement would be of very little use.

The important thing in O notation is not "how expensive is it" (because if that's all you're after, you can simply wait a year and buy a faster computer. Problem solved.)

It shows how fast the cost grows depending on input. If something runs in O(n) time, then it scales linearly with the size of input. It doesn't matter if it takes 1, 2 or 200 instructions per input "unit", all we're interested in is that the cost increases with the same amount when n goes from 2 to 3, as when it goes from 2000 to 2001.
So from that point of view, the constants can be simply ignored.

Similarly, if an algorithm runs in, say, O(2^n), we know that the cost is going to explode as n grows. It doesn't matter about the exact constants. We don't really care if we're really performing 2^n operations, or 10000 * (2^n). It's still going to blow up in our face very soon, unless the input size is always *very* small.
Again, it's the rate of growth we're interested in, not the factual cost for any specific input.


And yes, that means it's not a perfect measure. Sometimes, the constants do matter, and it may be better to use an algorithm that has a worth time complexity, because the constants are so much smaller that in practice, it usually ends up faster.
(A good example would be the quicksort algorithm, which is O(n^2) (or O(n*lg(n)) in the average case). Heapsort or mergesort are both O(n*lg(n)) in the worst case, so why don't we use those instead? Because in practice, quicksort performs really well. The hidden constants are pretty small, so for most common input sizes, quicksort is pretty damn fast.

There is some practical amiguity here.

While the O notation gives good general complexity, it's subject to implementation limitations.

This is very noticable with simple sorting algorithms. Most sorting algorithms have worst-case complexity of O(n^2), even the fastest. Yet in practice, they differ greatly.

An example of this is binary insertion sort. While on paper it looks like improved version of insertion sort ( binary search vs. linear for each element ), in practice the overhead not only makes it much slower for small lists, but also slower by a constant compared to regular insertion sort.

But what the notation tells you is how the algorithm scales.

n^2 is always much worse than n log n. Given high enough n, second will win, regardless of constant.

There are some exceptions. In certain very limited applications, the constant itself is the deciding factor.

But the bottom line is, the O notation describes the characteristics of the algorithm. That is one thing that cannot be changed. Implementation can be - faster chips, pipelining, memory cache, ... But the O cannot be changed without modifying the algorithm itself.

Quote:

Original post by TheUnbeliever I've been trying to better my computer science background for the past year or so, but I've come up against this paradox in my thinking. void Foo(int Input){ for (int i = Input; i < Input; ++i);} This is O(n) time, right?

Should be O(0) if you've got a competent compiler. [wink]

Thanks guys. Your posts, in addition to a little more thinking about it make it a lot clearer now. :-)

Quote:

Original post by Nathan Baum Quote: Original post by TheUnbeliever I've been trying to better my computer science background for the past year or so, but I've come up against this paradox in my thinking. void Foo(int Input){ for (int i = Input; i < Input; ++i);} This is O(n) time, right? Should be O(0) if you've got a competent compiler. [wink]

Heh, I did wonder if I should put in a disclaimer - but I decided I'd let someone pick me up on that. ;-)