# An Olog n example

## Introduction

Consider the following problem:

`L`

is a sorted list containing `n`

signed integers (`n`

being big enough), for example `[-5, -2, -1, 0, 1, 2, 4]`

(here, `n`

has a value of 7). If `L`

is known to contain the integer 0, how can you find the index of 0 ?

## Naïve approach

The first thing that comes to mind is to just read every index until 0 is found. In the worst case, the number of operations is `n`

, so the complexity is O(n).

This works fine for small values of `n`

, but is there a more efficient way ?

## Dichotomy

Consider the following algorithm (Python3):

a = 0 b = n-1 while True: h = (a+b)//2 ## // is the integer division, so h is an integer if L[h] == 0: return h elif L[h] > 0: b = h elif L[h] < 0: a = h

`a`

and `b`

are the indexes between which 0 is to be found. Each time we enter the loop, we use an index between `a`

and `b`

and use it to narrow the area to be searched.

In the worst case, we have to wait until `a`

and `b`

are equal. But how many operations does that take? Not n, because each time we enter the loop, we divide the distance between `a`

and `b`

by about two. Rather, the complexity is O(log n).

## Explanation

*Note: When we write “log”, we mean the binary logarithm, or log base 2 (which we will write “log_2”). As O(log_2 n) = O(log n) (you can do the math) we will use “log” instead of “log_2”.*

Let’s call x the number of operations: we know that 1 = n / (2^x).

So 2^x = n, then x = log n

## Conclusion

When faced with successive divisions (be it by two or by any number), remember that the complexity is logarithmic.