5
$\begingroup$

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ elements to process, even an $O(1)$ operation such as an index lookup will start to take longer as the index has to be calculated in multiple operations. I think it will take at least $O(\log n)$.

Similarly even if an algorithm has $O(\log n)$ complexity, $\log n$ cannot possibly grow larger than about a hundred, so could be ignored as no larger than a small constant.

So, is it really meaningful to treat $O(1)$ and $O(\log n)$ as different?

The same applies of any difference of $\log n$, like between $O(n)$, $O(n\log n)$ and $O(n/\log n)$.

$\endgroup$
  • $\begingroup$ Related, but not the same: cs.stackexchange.com/questions/1643/… $\endgroup$ – Tor Klingberg May 24 '16 at 16:05
  • 6
    $\begingroup$ 100 is not a small constant. If you have to use some piece of code in a tight loop having that 100x means your program goes 100x times slower. This is not good for, for example, any interactive use where you must perform certain operations in specific amounts of time and that 100x kills your goal. $\endgroup$ – Bakuriu May 24 '16 at 18:59
  • $\begingroup$ @Bakuriu Everything is relative. In contrast to your scenario, I might have some job that needs to be done once after a user has spent half an hour entering data. When they click the "submit" button, they're not going to care if it takes 1s to calculate the answer instead of 10ms. $\endgroup$ – David Richerby Jun 7 '18 at 15:42
11
$\begingroup$

There are actually all sorts of cases where $\log n$ gets way bigger than 100. For example, if you're working with variable-length integers - say, for cryptography - $\log n$ represents the number of bits in the integer, which can get up to 4096 or higher in practice. Those bits will be spread out over many machine words, so the $\log n$ term refers to how many machine words the number occupies and therefore definitely has an impact on the runtime.

Similarly, $O(1)$ does not mean "constant time only if $n < 2^{64}$." Yes, the computer has a fixed word size, but that doesn't mean that an $O(1)$-time algorithm given a gigantic input can't run in a fixed amount of time. Taking large integers as an example, consider the problem of checking whether an integer is even or odd. That just requires you to look at the last digit, which takes time $O(1)$ even if the number is spread out over thousands of machine words.

The last detail is that typically, we assume that we work with a machine model where the word size scales with the log of the size of the input. This allowance a to safely assume that you can do array accesses in time $O(1)$ because array indices are assumed to fit into a constant number of machine words.

$\endgroup$
  • $\begingroup$ You've just defined $n$ weirdly in your first example, as the value of the integer instead of the size. If you had been doing something $O(n)$ with that definition instead of $O(\log n)$, I'd be pointing out that it's really pseudopolynomial time instead of polynomial time, but "psuedologarithmic" doesn't seem to be a term in use. $\endgroup$ – user2357112 supports Monica May 24 '16 at 19:19
  • $\begingroup$ @user2357112 My understanding is that the convention in algorithms that work on large integers is that $n$ refers to the numeric value of the number in question, making $\log n$ its length. (I'm well-aware of pseudopolynomial time.) $\endgroup$ – templatetypedef May 24 '16 at 19:58
  • 1
    $\begingroup$ In the usage I've seen, $n$ has been the size rather than the value. $\endgroup$ – user2357112 supports Monica May 24 '16 at 20:00
  • 1
    $\begingroup$ Huh, that's weird - I've seen the exact opposite in number-theoretic algorithms. Though you're right - when it comes to multiplication, $n$ is usually the number of digits, while in crypto and number-theoretic algorithms it's usually the numeric value. I wonder why there's the split? $\endgroup$ – templatetypedef May 24 '16 at 20:06
  • $\begingroup$ The gist of this answer is right — the key is that the word RAM model makes log a constant, so to speak. But I don't understand where the part about working with variable-length integers is coming from. In crypto, like in information theory, complexity is always expressed as a function of the bit length. Expressing complexity as a function of the integers that the bits represent would be pointless. $\endgroup$ – Gilles 'SO- stop being evil' Jun 7 '18 at 20:08
7
$\begingroup$

There are several answers to your question. The first is: on such a finite machine, asymptotic notation makes no sense at all, and all algorithms have finitely bounded running time. That's a rather boring model, though.

so could be ignored as no larger than a small constant.

Why is 100 small? If my computer booted 100 times longer than it does I would be quite upset. Moden algorithm engineering fights for percents, and in scientific computing probably for fractions of that!

Also, don't forget that your logarithmic term may have another constant factor assigned to it. What if the running time is $\sim 10^{-10} \cdot n + 10^6 \cdot \log n$?

The same applies of any difference ...

There are people who dismiss polylogarithmic factors, probably for similar reasons than you do. They use the soft Landau notation to hide them away conveniently.

$\endgroup$
  • $\begingroup$ I don't understand your argument about "another constant factor". The given expression is $O(n)$, full stop. $\endgroup$ – Yves Daoust Jun 7 '18 at 15:50
  • $\begingroup$ @YvesDaoust But not everything is bout O-s. Which, as you'll note, doesn't really appear in my post. It's been a while, but I think I wanted to make the point that as soon as reality is concerned, O is mostly useless. I've made that point more eloquenty elsewhere since then. $\endgroup$ – Raphael Jul 15 '18 at 14:23
  • $\begingroup$ when a question is about Big Oh, it is about Big Oh. $\endgroup$ – Yves Daoust Jul 15 '18 at 17:13
  • $\begingroup$ @YvesDaoust The OP was clearly concerned with (real) computers, and stumbling over the fact that O-s don't carry meaning there. (Either way, what was your purpose in necromancing this? Is there an edit you'd like to propose? If not, I suggest we take the discussion to chat.) $\endgroup$ – Raphael Jul 15 '18 at 17:36
2
$\begingroup$

For not very large n, log n can be around 20. A factor log n matters about as much as it matters to have a computer built in 2016 and not one built in 1999.

On the other hand, O (n log n) can be faster than O (n) for practical n if the constant factor in the O (n) algorithm is say 50 times larger than for the O (n log n) algorithm.

A factor log n for say n ≥ 100 cannot be ignored if everything else is equal. Sometimes everything else is equal, sometimes it isn't.

$\endgroup$
  • 1
    $\begingroup$ Problems called large on today's personal computers are more on the side of $\log_2n=30$. $\endgroup$ – Yves Daoust Jun 7 '18 at 15:51
1
$\begingroup$

Saying $O(\log{}n)$ can't get above about 100 doesn't make sense when talking about about Big-O notation. The "$\log$" in $O(\log{}n)$ doesn't refer to any specific base. Big-O is about how the computational cost grows as $n$ gets larger, within a constant factor. Changing the base just changes that constant factor, so I can make the argument that $O(\log{}n)$ can be as arbitrarily large (or small) as you want to make it. But the growth stays the same! That's what's important when discussing Big-O. If you double $n$, the cost still increases in an $O(\log{}n)$ algorithm, unlike an $O(1)$ algorithm, but much less than the cost increase in an $O(n)$ algorithm.

The cool thing about $O(\log{}n)$ is that increasing the problem size makes it "easier" to increase the problem size even further. Increasing the problem size from $10^2$ to $10^3$ will increase the computational cost by $1/2$, but going from $10^3$ to $10^4$ will only increase the cost by $1/3$. So for very large $n$ the additional cost keeps decreasing, but it never reaches $O(1)$.

So no, $O(1)$ and $O(\log{}n)$ are not the same. In practice, which is faster will likely be problem dependent, but if it gets large enough $O(1)$ will win.

$\endgroup$
1
$\begingroup$

There can be. The obvious case is when $n$ is really huge. But there is another case which is very common. It depends on the constants involved. Let me give an example from data structure: a red-black tree has operations which are $O(\lg n)$. This seems good enough if the constants are small. However think about the situation where we have a huge amount of data in each node and we cannot keep the whole tree in the memory and have to use hard disks to store it. The access time to hard disk is huge compare to memory. Every access counts. If we have to access $\lg n$ times to the disk to get the value of the block we want it would be a huge drop in performance. That is the reason for data structure like B-trees. Not only $\Theta(\lg n)$ and $\Theta(1)$ differ a lot in practice even $2$ access and $3$ access can have a significant effect.

$\endgroup$
0
$\begingroup$

Consider a function:

int foo(int n)
{
    //mysterious code details
}

It can be implemented in a few different ways, and you've managed to come up with an easy algorithm in O(log(n)) but you think there might be a tricky one in O(1). You choose the easy path because there's not much of a difference, right?

Well, you're not looking at the big picture. Sean, the guy in the cubicle next to you, likes your function foo and decides he's going to use it in his code:

void main()
{
    print(bar(9999999999999));
}

int bar(int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                for (int l = 0; l < n; l++)
                {
                    sum += foo(i) * foo(j) * foo(k) * foo(l);
                }
            }
        }
    }
    return sum;
}

Do you think it matters now?

$\endgroup$
  • $\begingroup$ no. because no matter the implementation, sean's function will never return in your lifetime. also the difference is a factor ~13, excluding the possible constants. $\endgroup$ – njzk2 May 24 '16 at 19:51
  • $\begingroup$ @njzkw It matters to the aliens who come across the computer in the distant future. $\endgroup$ – Devsman May 24 '16 at 20:28
  • $\begingroup$ You wrote an algorithm that takes O ($n^4$ log n), when the same result can be trivially found in O (n log n). So the log n factor doesn't matter. $\endgroup$ – gnasher729 Jun 21 '16 at 22:04
0
$\begingroup$

The assumption "A computer can only process numbers smaller than say $2^{64}$" does not hold in the frame of asymptotic behavior computation. $n$ is considered unbounded and the algorithm runs on a theoretical computer with unlimited resources.

It is not the peculiar values of $f(n)$ that matter, but how the function grows with $n$.

If you take the finiteness of the representation into account, all algorithms are running in time $O(1)$, even the super-duper-exponential ones.

And in practice, an $O(1)$ algorithm can run much slower than a $O(\log(n))$ one.

May sound weird, but that's the way it is.


Final remark:

On modern machines, the access times to memory really depends on the number of elements. This effect has an effect much larger than $\log n$, so that relying too much on the idealized computer model is misleading.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.