# What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k.

Usually one traverses the "express line" (i.e. the top lane with least elements) first until you need to use lower lanes. This leads in the simple case of 2 linked-lists to a run time of:

$$L_1 + \frac{L_0}{L_1} = k + \frac{n}{k}$$

in computer science courses it is common to optimize this equation without using calculus. The equation that it leads to solve is:

$$k = \frac{n}{k} \implies k = \sqrt{n}$$

I was wondering if anyone remembered the alternative argument for optimizing the above equation?

If I recall correctly, it goes something like this:

we wish to choose a length of $L_1$ (i.e. k) that is as small as possible. But we also don't want it to be too small or $\frac{1}{k}$ will grow too much. So since the expression is sort of an "average" we just intuitively guess that its minimized that the "average" value. i.e. when $k = \frac{n}{k}$. I am not sure if this is completely correct or explained well but if someone remembers how to minimize this without using calc (as its usually taught in CS courses it would awesome!)

The method you mention is based on the following theorem:

If $f \geq 0$ is non-decreasing, $g \geq 0$ is non-increasing, and $f(t) = g(t) = y$, then $$y \leq \min_x [f(x) + g(x)] \leq 2y.$$

Note that there is (at most) a unique point $t$ such that $f(t) = g(t)$.

In your case, $f(k) = k$ is increasing and $g(k) = n/k$ is decreasing, and $f(\sqrt{n}) = g(\sqrt{n}) = \sqrt{n}$, so $\sqrt{n} \leq \min_k [k + n/k] \leq 2\sqrt{n}$. In fact, calculus shows that the minimum is indeed $2\sqrt{n}$.

The proof of the theorem is very simple: if $x \geq t$ then $f(x) + g(x) \geq f(t) = y$, whereas if $x \leq t$ then $f(x) + g(x) \geq g(t) = y$.

• 'Note that there is (at most) a unique point t such that f(t)=g(t).' That is wrong. if f=g=1 then f(t)=g(t) for all real numbers. There is at most one y but not one t. Dec 21, 2015 at 1:02

To make it more clear what is the constant and what is the variable I will use $x$ for the variable name instead of $k$ in the following. We will assume that $x>0$ and $n\gt 0$ and that the root $\sqrt{t}$ is the positive root of the positive number $t$.

We have $$x+\frac{n}{x}=\left(\sqrt{x}-\frac{\sqrt{n}}{\sqrt{x}}\right)^2+2\sqrt{n}$$ But $$\left(\sqrt{x}-\frac{\sqrt{n}}{\sqrt{x}}\right)^2 \ge 0$$ And its minimum 0 will be at $x=\sqrt{n}$

• Where is the trick, though? How do we know in advance that we need to solve $x = n/x$? Dec 20, 2015 at 17:25
• @YuvalFilmus: I am not sure if I understand you right. The trick is that a square is never negative. If $\left(\sqrt{x}-\frac{\sqrt{n}}{\sqrt{x}}\right)^2 =0$ for some $x=x_0$ then we have a minimum of $\left(\sqrt{x}-\frac{\sqrt{n}}{\sqrt{x}}\right)^2$ at this $x_0$ So we have to solve $\left(\sqrt{x}-\frac{\sqrt{n}}{\sqrt{x}}\right)^2 =0$ Dec 20, 2015 at 21:28
• There are many ways to solve this particular instance, for example using calculus. The question is why we expect the answer to be the solution of $x=n/x$. This is the trick - you don't need to optimize, only to balance the two terms. Dec 20, 2015 at 21:44
• @YuvalFilmus: If the OP asks "how to minimize this without using calc" then using calculus is not an option. But I read the question again and now I think the OP wants a proof without calculus as phrased in the last paragraph of th OP. And this 'proof' described in the last paragraph is what you call the 'trick'. I must think about this 'trick'. Dec 20, 2015 at 22:02