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