Math ∩ Reality

CS.

I don't think I've ever had such an intense argument about Big O.

Specifically whether an algorithm that is performed polynomial time constitutes being efficient.

I take my opposition's argument to be as such, it is considered technically feasible to solve any problem of NP class complexity (see Cobham's Thesis), therefore it could be considered a threshold for defining efficiency. In other words, it's a necessary condition.

My position is that Big O is simply a tool for analysis. Since there's so much context involved, an algorithm can't be considered efficient just because it computes in polynomial time. That is, not sufficient and not even a necessary condition. I'm not going to strawman here, so let's assume whatever program in question isn't racking up unnecessary cycles with a do{ }while(i<99999) or something equally asinine like that.

Case 1: If an algorithm has worst case O(k^n), but the chances of the worst case are 1 in a thousand, it may still be practical to take it over something with with a fixed O(n^2) time. Plus, in real life you can often choose to avoid worst case scenarios. For instance, a set may be sorted initially with a Quicksort implementation, but additional elements are added by Insertion.

Case 2: Coefficients are omitted from Big O, that's understandable from a mathematical stand point. From optimizing the algorithm (not with respect to hardware, just to itself), you might shave off a fraction of the computational time, but if you switch processors from a 386 to a Yorkfield cluster, the time is going to be reduced by magnitudes. That is what the coefficient represents. But you can't ignore coefficients in real life. Say your hardware performs a certain operation much faster than others and you're getting bottlenecked, it might be worthwhile to organize small chunks of your input even with an exponential time function because you're going to gain back that time in the end. In similar fashion, say you're bottle necked by memory and not processing power, it might make sense to write something that takes O(k^n) computing power and O(n log n) memory as opposed to something that takes O(n^2) of both.

As a minor point, my opponent argues that in an infinite set, polynomial time will always trump exponential time and for small sets efficiency doesn't matter anyways. But see, efficiency isn't relevant for small sets because the coefficient is 10 to the power of such a large magnitude (unless you're using a Celeron LOLOL) that it dwarfs everything else. If the coefficient makes that big of an impact, then it stands to say there may still be a large set less than infinity that computes faster with a routine in exponential time than one in polynomial time, depending on how it takes advantage of the hardware.

And realistically speaking, if your set is large enough to seriously look at Big O and your best case is O(n^3), you're probably in trouble anyways. Not to say you're not just as screwed with O(k^n), but now I'm back at the shot in the head vs shot in the chest analogy (see: last post).

For the record, the debate was ended by, "you see, I don't care about real life".

1. I know both Insertion sort and Quicksort are polynomial time operations. What I'm saying is, the latter averages O(n log n) while the former averages O(n^2), yet the former remains more efficient in some cases.

2. I also know Big O usually only refers to worst case, but lets not miss the forest for the trees shall we?

3. That is not to say computational analysis is useless. That's like saying what's the point of ideal gas law if gases aren't ideal? Well, if you're looking at nitrogen at 1 atm, 20°C you can guess that it's going to be a fairly accurate model. Ramp it up 400atm though, and it might be a good idea to break out the compressibility charts. ;)

4. I just wanted to put that chem analogy there. The fact is, the majority of the time polynomial time is preferable to exponential time in every way and Big O holds. But that's not what I'm arguing against.