0
$\begingroup$

Please refer here to the direct resource that I don't understand.

Let's take the number $X = 245436$, we can represent the following as $$X = 2 \times 10^5 + 4 \times 10^4 + 5 \times 10^3 + 4 \times 10^2 + 3 \times 10^1 + 6 \times 10^0$$ using decimal expansion. So, the minimum amount of information we need to represent this number is 6 digits. This is no coincidence, as any number less than $10^d$ can be represented in $d$ digits.

So how many digits are required to represent $X$? That's equal to the largest exponent of $10$ in $X$ plus $1$.

$$10^d > X\\ \log(10^d) > \log(X) \\ d\times \log(10) > \log(X) \\ d > \log(X) \quad\text{and log appears again...} \\ d = \mathop{\mathrm{floor}}(\log(x)) + 1$$

I can follow through his illustration and example, but it's the next example that confuses me. when he tries to relate searching for a number in a range from $0 \to N -1$.

Here's his explanation:

Taking $N = 10^d$, we use our most important observation:

The minimum amount of information to uniquely identify a value in a range between $0$ to $N - 1$ = $\log(N)$ digits.

This implies that, when asked to search for a number on the integer line, ranging from $0$ to $N - 1$, we need at least $\log(N)$ tries to find it. Why? Any search algorithm will need to choose one digit after another in its search for the number.

The minimum number of digits it needs to choose is $\log(N)$. Hence the minimum number of operations taken to search for a number in a space of size $N$ is $\log(N)$.

What I don't understand

This implies that, when asked to search for a number on the integer line, ranging from $0$ to $N - 1$, we need at least $\log(N)$ tries to find it. Why? Any search algorithm will need to choose one digit after another in its search for the number.

Specifically

Why? Any search algorithm will need to choose one digit after another in its search for the number.

Can someone show me an illustration of this?

If we had $10$ elements in an array ($n = 10$)

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

And I'm trying to find the what index gives me the value $5$? That means I need $\log(10)$ tries to find it? Firstly log of base $10$? That's $\log_{10}10 = 1$. I don't see how that makes sense? If I use base $2$ I get = $3$.

It means I'm taking a minimum of 3 operations to find x? Why? Can someone illustrate it?

I just don't see how the decimal expansion relates to finding a value in a range $0$ - $n$.

EDIT: the author made a video too but I still don't understand.

$\endgroup$
  • $\begingroup$ It would really be of great help if someone gave their input. $\endgroup$ – thatguyjono Sep 16 '19 at 15:10
0
$\begingroup$

i briefly read the article you directed to, its looks to me that he meant that even if you got your number, $N$, in first try, its still represented in $\log(N)$ digits, so you need to check every digit by itself to, and therefor it will take you at least $\log(N)$ tries. in your example, $5$ can be written in binary as $0101$ (as $floor(\log(10))+1$ equals $4$), and therefore, checking even the first element you'll need to check at least 3 digits of its to ensure it is the element you searched for

note: i using binary and log with 2 as a base, as usually used in computer science.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you illustrate how checking for the first element needs to check for at least 3 digits? Is it because of splitting the array in halve and checking the middle value every time? $\endgroup$ – thatguyjono Sep 19 '19 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.