# Why is one algorithm faster than the other if both have performance of O(1)

If I have a very large number X, `(978678567445456455878909099775523213255436445691200897623461676543789287 948754875435250392049320487584759329 454754875487589457244076477592458249)`

And I have two algorithms that can compute whether or not the the input number is divisible by 4 (i.e. n % 4 == 0). Since the modulo operation takes O(1), why would one algorithm be better than the other if they are both O(1). How could I prove that the one which only compares the last two digits(2) is in fact better than the other?

algorithm 1:

``````n:= Input
if n divisible by 4, let output :=0
else output :=1
``````

algorithm 2:

``````m:=last two digits of input n
if m divisible by 4, let output:=0
else output:=1
``````
• You don't seem to understand what O(1) means. If you want to compare two algorithms, you should err.. test them:) – Martin James May 11 '16 at 0:39
• O(1) describes a function that relates input size (number of bits) to run time. In particular, it says that the input size doesn't affect the run time. It says nothing about the run time itself. So one O(1) algorithm may produce an answer in one millisecond and another in 10,000 years. Which one do you think is "better?" Moreover, as others have pointed out, the modulo operation is not O(1) for any realistic machine model. I.e., the size of the input matters very much indeed. – Gene May 11 '16 at 5:20

## 2 Answers

1. Algorithm 1 is not O(1). It's running time is proportional to the number of bits of the input number, so it is O(log `n`).

2. It makes no sense to talk about the running time of a function with constant input. Running time is about asymptotics, not about how long it takes for a specific single instance.

3. Big O notation does not distinguish between constants. Instead, two running times are the "same" only if they are within a constant multiple of each other. In other words, even though two algorithms may have the "same" big O notation (actually big theta notation if we want to be more precise), one might actually be a constant times faster than the other in the asymptotic case.

• Thankyou, but why is it O(log n) and not simply O(n) if proportional to number of bits? Is this because the modulo function is a involves division? – Als May 11 '16 at 11:55
• @Als because n has O( log n ) bits (more precisely, it has log base 2 of n bits) – TheGreatContini May 11 '16 at 12:14
• Since the number in the OP is denoted by `X` wouldn't it be reasonable to replace `O(log n)` by `O(log X)`? In fact, since `n` usually denotes the input size, I would assume `n = log X`. – Dmitri Chubarov May 12 '16 at 7:14

Depending on the key type a C++ Map is considerably faster at finding things for small datasets than it's Hash. The Map is O(log n) and the Hash is O(1). The reason is Big O is dealing with the asymptotic performance of the algorithm ie if we plot the performance of the algorithm with some ever increasing value of `N` what curve does it approach.

When we hash something like a string we likely compute each byte in turn. That could 10 or 100 bytes where we need to perform some form of computation to find the bucket where the item is to be stored. Note however that this computation is a fixed size. As the number of strings `N` is increased it in no way affects the computation of the hash ie `N` is not impacting the time to find the bucket and insert the item. If you plot it as `N` increases the time to hash the function and locate a bucket is constant ie O(1)

When we use a Map we need to compare each string against the next one in the tree. This time as we add strings to the tree we have more strings we need to compare against ie as `N` increases we're in some way affecting the amount of comparisons that we need to make in order to find or insert a string. When there are a few strings in the Map this is actually faster than a Hash (Note, It was for me a few years ago using C++ and Urls, not sure if it's still the same now). This is because for a few strings it needs to do less work than the Hash does. This time because it's a binary tree we have a logarithmic affect ie the amount of computation required is increasing and if you plotted it you'd find it's following a logarithmic curve ie it's O(log n).

The reason is that Big O is not about fixed sized datasets it's about describing the behavior of an algorithm as `N` increases.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}