Main Question:

Say I have some algorithm, that runs in O(n^2).

I get that, if I input an n twice the size of the original n I get 4 doubling of the maximal time complexity.

But how does it relate to running the algorithm twice with an input size of n?

Why I am asking:

The reason for why I'm asking, is because I made an algorithm whose big O notation was O(log_2(n)). But running it and comparing it to O(log_2(n)) showed, that it performed FAR better for inputs at the magnitude of 1 billion. The algorithm would only be used on inputs the size of 10k-20k. Meaning that it performed wastly better than $C_1*log_2(n)$

I get that big O notation is the maximum, but it felt like I asked "How tall are you?" and the big O notation answered "I am shorter than 40 meters".

I googled around a bit and found, that big O is - "in industry" - primarily used for scalability. I.e you expect your n to reach that point where it will get close to its big O.

Then, in my case, does it even make sense to use big O notation? How does running the same algorithm multiple times, rather than increasing the input size, relate to big O notation?

CodePudding user response：

The bad news is that the asymptotic complexity formulas don't help predict the running-time of algorithms for practical N (I would even dare say do not help at all).

Because for small N, the running time is usually dominated by the low-order terms of the complexity.

And for larger N, the RAM model (constant-time access to any address) is irrelevant. The access time can vary by several orders of magnitude due to cache and virtual memory effects !

Also note that big-O analysis relates to the worst-case complexity, which can be very far from the cases you try. Even expected-case complexity may be irrelevant, because it relies on a specific input distribution, which can be unrealistic, and dispersion can be large.

CodePudding user response：

is there then anymore I can gather from the algorithm being O(log(n)) other than, it will be faster than that in the long run?

Time required by an implementation of an O(log n) algorithm will grow very, very slowly with problem size. It will not become faster with larger problem sizes, but the growth will be minimal.

Or would it be "useless" for me to use in practice, with input sizes of my dimension?

It depends on the available alternatives. If there is a faster but "worse" (big-O-wise) algorithm, it can make sense determine the input sizes where implementations of each are faster. An O(log n) will, however, always win over, say, O(n) algorithms in the long run (for big enough n). If there is no faster alternative, why worry? O(log n) is good to have, even if you do not "need" it.

Big-O only helps you to choose algorithms that can scale as expected as problem sizes grow. An algorithm's big-O class says nothing about how well a specific implementation of that algorithm will perform for a specific input on a specific machine. Indeed, it is frequent to use "bad" algorithms (with, say, O(n^2) complexity) instead of "good" algorithms (say, O(n log n)) for smaller problems, simply because they will be faster for those input sizes. Look at sorting: many implementations of quicksort fall back to insertsort for very small inputs:

This line in java's standard library source-code comes to mind: its authors have experimentally determined that, for arrays of less than 7 elements, insert-sort is quicker than quicksort.