0

We want to minimize the equation below with respect to r.

$$\frac{b}{r}(n+2^r)$$

where b is a constant.

The professor suggested we take the derivative of the equation, set it equal to 0, and then solve for r.

By using the quotient rule and chain rule, I came to the conclusion that the derivative of the equation above is:

$$\frac{b(2^rrln2-n-2^r)}{r^2}$$

But from this point I'm unsure how to solve for r.

EDIT

The answers below are what I found on WolframAlpha as well, but they make me think something has been done incorrectly. This equation is supposed to represent an ideal r value for an equation that is an analysis of an algorithm, so having n=0 be the only case where an actual value is identifiable wouldn't be of much use. I also don't think he would assign this with the intent of us ending up with the Lambert-W function. He seemed like he was expecting a value.

Below I've included all the information I have, just in case I'm misinterpreting something.

$$T(n) = [\frac{b}{r}[n+2^r]]$$ We want to find the best size r, that is, we want to minimize T(n) with respect to r. Take the derivative of T(n) with respect to r. Where n is the number of entries, d is the number of digits per entry, and d is equal to b/r, where b is the number of bits in an entry. This is the equation representing an analysis of Radix sort, if that helps.

Ryan
  • 1,651
  • Is $n$ a constant too? – Calvin Lin Sep 24 '13 at 00:56
  • I didn't think so, but reading over the notes again, it may be. We're trying to minimize T(n), where T(n) is the first equation shown. – Ryan Sep 24 '13 at 01:03
  • It sounds like $ T(n) = \min \frac{b}{r} ( n + 2^r)$. If so, then for the purposes of finding the minimum, $n$ is a constant. – Calvin Lin Sep 24 '13 at 01:04
  • I think you're right. n appears to stand for the number of entries. I'm not sure where that leaves me. The n still drops out when doing the quotient rule for (n+2^r), and I believe it would still be present on the other side of the quotient rule where the derivative of (n+2^r) is not taken. – Ryan Sep 24 '13 at 01:14

2 Answers2

1

WolframAlpha gives the answer in terms of the Lambert-W function: $$r=\frac{1+W(n/e)}{\ln(2)}$$ which may or may not be an acceptable answer for you. In any case, this means there is probably no "elementary" solution (i.e. in terms of the four operations, powers, roots, and logs), so if you want something more concrete you are looking for a numerical answer.

For that, you should plug in $y=\displaystyle\frac{b(2^rr\ln2-n-2^r)}{r^2}$ to your favorite graphing utility (with values of $b$ and $n$) and use that find a zero of this function.

[ There are series representations, but they're horrendous. ]

Eric Stucky
  • 12,758
  • 3
  • 38
  • 69
1

I'm assuming $n$ is a constant, too.

Your expression set equal to zero has no explicit analytic solution in general. You can express its solution implicitly, express its solution explicitly with an implicit function (in this case, the Lambert W function), or solve it numerically (in this case, for different values of $n$ and $b$). Following my second suggestion, the solution for your problem is $$ r= \begin{cases} \frac{W(\frac{n}{e})+1}{\ln{2}}, & n\neq 0\\ \frac{1}{\ln{2}}, &n=0 \end{cases} $$ where $e$ is the usual exponential constant and $W$ is the Lambert W function. Of course, you may need to evaluate this expression numerically anyway depending on your intended use.

verbaetlittera
  • 111