| Criterion | Which is best? |
|---|---|
| Generality | linear |
| Effectiveness | either |
| Termination | either |
| Efficiency | binary |
| Elegance | binary |
To determine the efficiency of the algorithms, we need to consider their computational complexity ("big O notation"").
A search may or may not be successful. There is not necessarily any guarantee that the item being sought is present in the array.
In the tables below:
| best case | 1 |
| worst case | N |
| average case | Ps(N/2) + Pu(N) |
| average case | N/2 (where Pu=0) |
Since all cases but the best case have complexity proportional to N, we say that linear search is an "order N" algorithm.
O (N)
| best case | 1 |
| worst case | log N |
| average case | ~log N |
| average case | ~log N (where Pu=0) |
O (log N)