Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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 :)

share|improve this answer
    
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! –  mtreit Oct 16 '10 at 6:37
    
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}$ –  WWright Oct 16 '10 at 6:46
    
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? –  mtreit Oct 16 '10 at 8:03
    
@mtreit What makes you think $2^{\log_2(10)} = 10$ isn't true? It certainly seems true to me... –  Alex Basson Oct 16 '10 at 12:56
    
Perhaps these online tutorials can explain it better than I can: wtamu.edu/academic/anns/mps/math/mathlab/col_algebra/… –  WWright Oct 16 '10 at 15:47
show 2 more comments

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).

share|improve this answer
    
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. –  mtreit Oct 16 '10 at 6:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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