Which Algorithm is faster?

Question

Our Lecturer gave us his code

procedure linear_search (x: integer; a1, a2, …, an: integers)
   i := 1
   while ( i ≤ n and x ≠ ai )
     i := i + 1
     if i ≤ n then
        location := i
     else
        location := 0

and this is mine

method Search (x integer, a1,a2....an integers)
   for i from 1 to n
   start
       if ai = x, location = i, break.
       else i++, location = 0.
   stop

In terms of steps, my code takes 2n + 1 steps to finish while the other code takes 2n + 2, therefore my code is logically faster. However, in Big O terms, they're both O(n). So what do I say, which one is faster? Or do I say they're equal?

Answer 1

As far as big-O is concerned, the two are equal: you can freely subtract constants and divide by constants, so both algorithms are linear in the number of their inputs - i.e. they are O(n).

In general, big-O will not tell you exactly how fast an algorithm is. It boils everything down to a formula that describes how fast would performance or memory consumption degrade if you were to increase the size of the input, giving you a measure suitable for comparisons.

This by no means provides a complete picture, only a rough estimate. Other important things, such as cache and branching efficiency, can make one program much faster than the other program, even when they both implement algorithms with the same big-O efficiency measure.