10

Can somebody give me a realistic example in which an O(N*N) algorithm is faster than an O(N) algorithm for some N>10.

EDIT : I see this question being put on hold for being too generic. But i do have a generic question only. There is no other way that this question could have been asked in a different way.

Darwin von Corax
  • 5,201
  • 3
  • 17
  • 28
anurag86
  • 1,635
  • 1
  • 16
  • 31
  • 2
    Is this a class assignment? – Topological Sort Oct 26 '15 at 18:18
  • 1
    Not `O(n^2)` vs `O(N)` but a bubble sort is faster than quick sort when the size of the data is small as the overhead for the quick sort outweighs the speed of the bubble sort. – NathanOliver Oct 26 '15 at 18:18
  • No this is a question from bjarne stroustrup's book - The C++ programming language, and i cannot even imagine how it will be ever possible. – anurag86 Oct 26 '15 at 18:18
  • 1
    Are the answers not in the back? How is doing the exercises supposed to help if you just ask on here? – Useless Oct 26 '15 at 18:19
  • 1
    If the constant was huge. As in `bubble sort` vs `find largest` where every loop iteration in the latter needs to read from a hard disk. – Ryan Haining Oct 26 '15 at 18:19
  • 3
    Yes: Counting-Sort, when the amount of elements is small, but the range is large (since you need to iterate all the entries in the histogram). For example, consider counting-sort of the elements `4,8,6,2,999999`. You'd need to scan a million-entry array in order to complete this type of sorting, but you can perform any "standard" sorting in about 5*5 iterations. – barak manos Oct 26 '15 at 18:20
  • Remember that O() only denotes the upper bound. – Caleb Oct 26 '15 at 18:29
  • 1
    One example that comes to mind is that the simplex method has a larger upper bound on complexity than some other algorithms yet in practice it runs much faster than those algorithms. In most of the cases I have gone with using a higher upper bound it has been because of average case considerations. – shuttle87 Oct 26 '15 at 18:29
  • 2
    Another stroustrup gem is the O(1) list operations as opposed to O(N) vector operations where the list is far slower (due to caching) – Ryan Haining Oct 26 '15 at 18:29
  • It's easy to demonstrate that O(1) can be slower than O(log(N)) or O(N). Read a file sequentially and search M sequential items linearly. Compare that to calculating a hash function and loading the respective records from the file individually. O(N) will be hundreds of times faster than O(1) in this case. Analogous for any algorithm on any significant amount of data where VM effects of some sort (faults, TLB, caches) may come into play. If O(1) can be shown to be slower than O(N) then O(N) can be slower than O(N*N), too. – Damon Oct 26 '15 at 18:31
  • @Ryan Haining : the caching example you gave is more of a architecture dependent problem(and proof) rather than pure algorithmic. – anurag86 Oct 26 '15 at 18:39
  • The architecture contributes to the constants attached to the big-O – Ryan Haining Oct 26 '15 at 18:41
  • 1
    The classic example of an algorithm with better Big O notation that only outperforms the naive implementation for gigantic numbers is probably multiplication. Schönhage–Strassen apparently outperforms Karatsuba only for n of 2^2^15 and larger. Same goes for Karatsuba when compared to the naive grade school algorithm (although that one has a much lower cutoff).# – Voo Oct 26 '15 at 18:51
  • `f(n) = c1 * n * n; g(n) = c2*n;` solve for `f(n) = g(n)` for `n > 10.` – Alexandru Barbarosie Oct 26 '15 at 23:03
  • @Alexandru Barbarosie : do you mean to say solve for `f(n) = g(n)` or `f(n) < g(n)` for n > 10 to have O(N*N) better than O(N)? In the latter choose any big c2>10 and a very small c1>10. If for n=11, c1=10 and c2=1000 then `f(n) < g(n)` – anurag86 Oct 27 '15 at 06:27
  • One thing to note is that `1 = O(N*N)` and `N = O(N)`, but clearly `1` is 'faster' than `N`. This can matter in situations where the `O` is meant seriously, rather than because the author should have written `Θ`. (that's a Theta) –  Oct 27 '15 at 12:30
  • Think Aeroplane vs Bicycle. The first is faster... except if you only need to go a couple of blocks, in which case you should not want to deal with the constant waiting time at the aeroport. – v010dya Oct 27 '15 at 15:17
  • @Damon : For reading a file sequentially it would be a O(N) operation? What is O(1) you are referring here to? – anurag86 Oct 28 '15 at 14:51
  • @anurag86: Reading a file sequentially is de-facto O(1) since the operation is limited by access time, not bandwidth. Doing one read worth 4kB takes approximately (indeed under e.g. Windows and Linux _exactly_) the same time as doing a 64kB read, and reading 1MB only takes very, very little more time (practically the same). Doing three reads takes three times as long as doing one. Doing 50 reads takes 50 times as long. Pulling a 100MB file into memory (or memory mapping it and iterating over the data linearly) takes about a second on a typical drive. On the other hand, – Damon Oct 28 '15 at 17:31
  • a non-sequential access pattern with 100 accesses only a few bytes in size on the same file will _also_ take one second, and 200 accesses will take twice as much time. It scales O(N) with the number of accesses. – Damon Oct 28 '15 at 17:32
  • math: solve `Ax + B = Cx^2 + Dx + E` or just `Ax = Bx^2 `. Or just draw a Parabola and a line and see where they intersect and notice that for some range of values the parabola is below the line. – Z boson Nov 24 '15 at 09:31

4 Answers4

2

It could be that some tried to make a O(N*N) algorithm faster (e.g. by introducing some preconditioning of the data) and ends up with something like this:

O(N):

for (int i=0;i<N;i++){
    // do some expensive preconditioning of your data
    // to enable using O(N) algorithm
}
for (int i=0;i<N;i++){
    // run the actual O(N) algorithm
}

O(N*N):

for (int i=0;i<N;i++){
    for (int j=0;j<N;j++){
        // run the O(N*N) algorithm
    }
}

The big O notation is only the limiting behavior for large N. The constant (or linear) part can differ a lot. For example it might be that

O(N)   =           N + 10000 
O(N*N) = N^2 + 0.5*N +    10
463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • "The big O notation is only the limiting behavior for large N. The constant (or linear) part can differ a lot." -- I don't understand what you're trying to say here. – David Titarenco Oct 26 '15 at 18:30
  • @DavidTitarenco better? – 463035818_is_not_an_ai Oct 26 '15 at 18:33
  • A good example might be finding duplicates in an array. Adding all the elements to a counting-set and *then* checking for counts > 1 is O(n), but it will be slower than a naive comparison-based algorithm that usually finds duplicates very early on. (e.g. because there are only 26 letters in the alphabet). Similarly, MergeSort uses InsertionSort for small subproblems. big-O notation only tells you which algo will win at N=infinity. – Peter Cordes Oct 27 '15 at 06:43
  • 1
    Why downvotes without comments? I would fix if I knew what is wrong but as I dont know what to fix I might simply delete it... – 463035818_is_not_an_ai Oct 27 '15 at 08:45
  • @Peter Cordes: So the bottom line is that the constants might make O(N*N) work better than O(N). Big O just tells the worst case scenario. It doesnt mean O(N*N) will always be O(N*N).E.g. I try to find a number in an array of million elements. Worst case would be that the number to be found is at the end. But still the number could be in the beginning. Is this the gist of all the answers? Is my understanding correct? – anurag86 Oct 28 '15 at 14:42
  • @anurag86: yes, something like that. It can be useful to talk about the time for the average case being O(n log n), but worst case O(n^2), for quicksort for example. big-O doesn't have to be a tight bound, either. Any algorithm in the O(n) complexity class is also a member of the O(n^2) complexity class. But it tends to get used in casual discussion in places where people really mean big-Omega. – Peter Cordes Oct 28 '15 at 14:52
  • Anyway, comparing two algorithms only by their big-O time complexity tells you which will be best at N=infinity, nothing more is guaranteed. Usually the algo with the better complexity wins at reasonable size, but there are theoretically-better algorithms that just don't do well on actual hardware, and aren't faster in real life until uselessly-large problem sizes. – Peter Cordes Oct 28 '15 at 14:53
  • Totally understand it. Thanks a lot :) – anurag86 Oct 28 '15 at 14:56
1

Can somebody give me a realistic example in which an O(N*N) algorithm is faster than an O(N) algorithm for some N>10.

The big O notation describes only the asymptotic performance of an algorithm, with N tending toward the positive infinity.

And most importantly: it describes the theoretical performance of the algorithm - not of its practical implementation!

That's why the constants and the minor functions, relating to other overheads, are omitted from the big O notation. They are irrelevant for the shape of the major function (especially when N tends to infinity) - but they are crucial for the analysis of real world performance of the implementation of the algorithm.

Simple example. Put sleep(60) inside the qsort() function. Asymptotically the algorithm is still the same O(N*log(N)) algorithm, because the constant 60 second sleep is minuscule compared to the infinity. But in practical terms, such qsort() implementation would be outran by any bubble sort implementation (without the sleep() of course), because now in front of the N*log(N) stands huge constant.

Dummy00001
  • 16,630
  • 5
  • 41
  • 63
0

Input is an integer n.

First example: a pair of short programs that use the fact that O notation is an upper bound, so a program that is O(1) is also O(n) and O(n^2), etc...

Program 1: 

def prog1(n)
    1.upto(n) do |i|
    end
end

Program 2:

def prog2(n)
    return
end

Program 1 is O(n) and program 2 is O(n*n) as well as O(n) and O(1) and O(n^n^n^n^n).

Yet program 2 is faster than program 1.

Second example: A pair of programs that use the fact that O notation depends on behavior as n gets big.

Program 1: same as before

Program 2:

def prog2(n)
    if n < 10^100
        return
    else
        1.upto(n) do |i|
            1.upto(n) do |j|
            end
        end
    end
end

Program 1 is O(n) and program 2 is O(n*n).

Yet program 2 is faster than program until n >= 10^100.

Dave
  • 7,460
  • 3
  • 26
  • 39
  • No i didnt understand how is your second program O(n*n)? It doesnt have to do anything with what arg you are getting. – anurag86 Oct 26 '15 at 18:47
  • 1
    Because everything in O(n) is in O(n^2), and everything in O(1) is in O(n) – Chad S. Oct 26 '15 at 18:51
  • @anurag86 O notation gives an upper bound. Theta gives a tight bound. Omega gives an upper bound. If something is O(f(n)) then it is also O(g(n)) for all g >= f (i.e. lim n -> infinity of g(n)/f(n) >=1 – Dave Oct 26 '15 at 19:57
  • Whoops. I meant to say that omega gives a lower bound. – Dave Oct 26 '15 at 20:28
  • 1
    This is a correct but useless answer. Clearly the OP was thinking of O(n^2) being a tight upper bound on the run time of the O(n^2) algo. If you wanted to nit-pick about using big-O instead of big-Omega, you should have just said that. example code isn't needed. – Peter Cordes Oct 27 '15 at 06:38
  • 3
    @PeterCordes I disagree. Someone confused about what big-O means, and there are plenty of them, will be likelier to learn that it's an upper bound if they see a concrete example, though I should have said so in my answer instead of in a comment. – Dave Oct 27 '15 at 11:59
  • Good point, an initially-confusing example will probably get them thinking. Your second example is still intentionally perverse. You couldn't use something along the lines of what the OP was looking for, like insertion-sort for small sub-problems of a divide-and-conquer O(n log n) sort? – Peter Cordes Oct 27 '15 at 14:00
  • @PeterCordes Examples taken from algorithms that are actually used will be much more complex, which I don't think would be helpful. Maybe A better second example might have been to make the slower algorithm straightforward and give the faster one some up-front work to do to represent the class of fast algorithms which require a lot of pre-processing so are only useful for large n. – Dave Oct 27 '15 at 14:40
  • I'd go with a O(n) with a large constant factor, vs. O(n^2) that has low overhead and good cache behaviour. I guess if you insist on full detailed code, that limits your options for keeping the examples small, though. An O(n^2) worst case that usually exits early might be worth mentioning. (see my comments on another post on this question). – Peter Cordes Oct 27 '15 at 14:50
0

As a realistic example, see my answer to this question.

Median of N numbers can be found in O(N) time (either in worst case, or on average). For example, such an algorithm is implemented in std::nth_element.

However, for small N a proposed algorithm with O(N^2) complexity can run faster, because 1) it has no branches, 2) it can be vectorized with SSE. At least, for N=23 elements of short type, it outperforms std::nth_element in 4-5 times. This particular setting has its application in image processing.

P.S. By the way, implementations of std::nth_element usually use insertion sort internally when N <= 32, which is also an O(N^2) algorithm.

Community
  • 1
  • 1
stgatilov
  • 5,333
  • 31
  • 54