# log to the base 2

#### How many times can you divide N things in half?

N/2/2/2/2/2/2/.../2 = a
|_________________|
k times

N * 2^{(-k)} = 1
N = 2^{k}

k = log_{2}(N)

#### How many accesses will it take to find X as we increase N ?

N
| log_{2}(N) |

1
| 1 |

10
| 3 |

100
| 7 |

1000
| 10 |

1000000
| 20 |

Last Modified -