Question

a.One important application of logarithms is found in various computer search routines. For example, a binary search algorithm on a table (or array) of data takes a maximum of log2n (“log base 2, of n”) steps to complete, where n is the number of data elements that can be searched. How many steps (at most) are needed for a search of a table with 16 elements? 512 elements? Explain

Answer 1

I need to know how to come up with the answer without using a calculator

Answer 2

My answer are:
log(base 2) 16 = 4
log(base 2) 512 = 9

2^4 = 16
2^9 = 512

i dont know how to explain though. i guess you would have to relate this with exponents.

Answer 3

\[\log_{2}n = x \]
Here,
\[2^x = n\]

It's just a matter of knowing your powers of 2.

Answer 4

So to hit a BST of 16 elements, the tree height will be at most 4.
For a BST of 512 elements, the tree will be at most 9 high.

Answer 5

Thanks. Putting it in an exponential form gives me a better way of looking at it.