1
$\begingroup$

I'm trying to understand the approach to calculating an answer to the following question.

I need to do some processing on a list of n items. I know that the total processing time takes $\log_2 (n)$ milliseconds.

Problem: What is the maximum number of items that can be processed in $10$ seconds (i.e., $10,000$ milliseconds) ?

What is the right general approach / technique? I should mention that I am a math neophyte.

It's clear that if I have a list of $1,000,000$ items it will take $13.8$ milliseconds, as $\log_2(1000000) = 13.8$.

What's not clear is how to compute the maximum n that can be processed in $10,0000$ milliseconds. I know it's a gigantic number, but I am not sure how to calculate it. If the number was small I could probably find it by trial and error, but:

A) It's a giant number such that trial and error seems impractical.

and

B) Even if it was not so huge, I'd really like to understand how to compute it deterministically rather than by experiment.

Thanks very much for any pointers.

2 Answers 2

3

If I understand your question you want to solve an equation of the form: $\log_{2}(x)=100,000$

The key to this is exponentiation

In your case we want to do the following:

$2^{\log_{2}(x)}=2^{100,000}$

which simplifies to

$x=2^{100,000}$

which is quite a large number as you correctly predicted :)

  • 0
    Thanks very much, I think I just need to bone up on exponentiation as you say. It's not immediately clear to me why $2^{\log_{2}(x)}$ simplifies to $x$ but that seems like a simple enough thing to go study up on and understand. Certainly once that is clear then the answer to my problem is easily calculated!2010-10-16
  • 0
    That follows because $g(x)=\log_{2}(x)$ is the inverse of $f(x)=2^{x}$ and more generally $\log_{a}(x)$ is the inverse of $a^{x}$2010-10-16
  • 0
    I must be misinterpreting something, please bear with me. Your answer states that $2^{\log_{2}(x)}$ simplifies to $x$. Assume $x = 10$, then you seem to be saying that $2^{\log_{2}(10)} = 10$...which isn't true. Does your original answer have a typo?2010-10-16
  • 0
    @mtreit What makes you think $2^{\log_2(10)} = 10$ isn't true? It certainly seems true to me...2010-10-16
  • 0
    Perhaps these online tutorials can explain it better than I can: http://www.wtamu.edu/academic/anns/mps/math/mathlab/col_algebra/col_alg_tut45_expeq.htm2010-10-16
  • 0
    Alternatively, you may want to look at the graphs of $2^{x}$ and $\log_{2}(x)$ and see that they are reflections of each other about the line y=x. I think this is probably the most intuitive way to think about it.2010-10-16
  • 0
    Argh, you're right, I was using log not log2 by mistake. Thanks very much for your help and patience.2010-10-16
0

When I read the headline I thought you were asking about the knapsack problem, but then I read your question and it turns out you are just asking for an inverse to binary logarithm.

The problem asks "find $n$ such that $\log_2 n \geq 10^4$." Note that $\log_2 x \geq y \Leftrightarrow 2^{\log_2 x} = x \geq 2^y$ because $x \mapsto 2^x$ and $\log_2$ are monotonely increasing. This should be enough for you to figure out the answer (and yes, it is huge).

  • 0
    Thanks kahen. My math knowledge is sufficiently limited that I don't quite follow your explanation, but I think it's pointing me in the right direction.2010-10-16