2
$\begingroup$

Suppose we have algorithm that is $\Theta(n(t+n^{1/t}))$, where $t>0$ is some parameter. How to select $t$ such that the running time has a minimum rate of growth?

Source: Combinatorial Optimization by Korte and Vygen (I am going through this book by myself but sadly there are no available solutions anywhere online, it seems).

I am not very proficient with math, but my assumption is that I need to look for $t$ s.t. the second derivative of $n(t+n^{1/t})$ would be 0 (since we are looking for minimal RATE of growth, not for the minimal value of the function itself, so $n^{1+1/t}ln^2(n) = 0$.

Is that a correct approach, or I completely misunderstood the question/concept of the rate of growth?

$\endgroup$
2
  • 3
    $\begingroup$ You want to minimize $t + n^{1/t}$ over $t$. So you want the first derivative with respect to $t$ to equal 0. $\endgroup$ Mar 19 '20 at 13:02
  • 1
    $\begingroup$ Alternatively, you can get a solution which is optimal up to constant factors by solving $t = n^{1/t}$. $\endgroup$ Mar 19 '20 at 13:02
3
$\begingroup$

Here is the original exercise.

Suppose we have an algorithm whose running time is $\Theta(n(t + n^{1/t} ))$, where $n$ is the input length and $t$ is a positive parameter we can choose arbitrarily. How should $t$ be chosen (depending on $n$) such that the running time (as a function of $n$) has a minimum rate of growth?

As others have pointed out, you misunderstood the exercise. The phrase "rate of growth" is indeed somewhat misleading.

The rate of growth of the running time of an algorithm refers to the growing behavior of the running time when the input length goes bigger and bigger. It is almost universal trend that the running time of an algorithm becomes longer when the input length becomes bigger. In particular, it is true asymptotically for the current case if we assume $t$ is a constant.

In order for the running time to have a minimum rate of growth everywhere or in average, we need the running time be the minimum when the input length is sufficiently large, since the running time for input length $n$ is the sum of all differences between the running time for input length $i-1$ and $i$, where $i$ ranges through $n_0$, $n_0+1$, $\cdots$, $n$ for some small constant $n_0$ and the running time for input length $n_0$. So, the requirement "the running time (as a function of $n$) has a minimum rate of growth" in general is just "the running time (as a function of $n$) is the minimum", as we ignore the contribution of the usually rather short running time for the small input length $n_0$. The exercise would have been clearer had it said "... such that the running time is the minimum as a function of $n$".

"How to select $t$ such that the running time has a minimum rate of growth?" The definition of $\Theta$ tells us that the running time is proportional to $n(t+n^{\frac 1t})$ within a constant factor. This question requests you to select $t$ as a function of $n$ such that, $n(t+n^{\frac 1t})$ as a function of $n$ is as small as possible. Or, once we have pulled out the factor $n$, such that, $(t+n^{\frac 1t})$ as a function of $n$ is as small as possible


Now that we have understood the exercise, the real task is how to answer that question.

Note that $t$ increases as $t$ increases. On the other hand, $n^{1/t}$ decreases as $t$ increases, assuming $n>1$.

If we let $t=1$, then $t+n^{\frac 1t} = 1 + n$. If $t=n$, then $t+n^{\frac 1t}=n+n^{\frac 1n}= n+o(1)$. In either case, either $t$ or $n^{\frac 1t}$ is rather substantial. If we select $t$ to be some value between $1$ and $n$, we could possibly make both $t$ and $n^{\frac 1t}$ much less substantial, thus making their sum much smaller. The relevation is that we could choose $t$ such that $t=n^{\frac 1t}$ so that none of the two is particularly large.

Suppose $t_0$ as a function of $n$ satisfies $t_0=n^{\frac1{t_0}}$. Then we have $$t_0\le\min_{t>0}t+n^{\frac 1t}\le 2t_0$$

It is an easy exercise for the interested readers to prove the above formula.

The above formula indicates that we can use binary search to find or approximate the wanted value of $t$. Fixing $n$, we will start with interval $[1,n]$. Check the middle value $t =(1+n)/2$. If $t<n^{\frac1{t}}$, replace the left endpoint 1 with $(1+n)/2$ so that we will continue with interval $[(1+n)/2,n]$. Otherwise, replace the right endpoint n with $(1+n)/2$ so that we will continue with interval $[1, (1+n)/2]$. Repeating this binary search until the interval becomes small enough. We will use either of its endpoints as the wanted value of $t$.


The above gives a simple algorithmic way to chose $t$ to make $t+n^{\frac1n}$ reach the minimum within a factor of 2. We can do better following the steps given by D.W.

You want to find $t$ that minimizes $f(t)=t+n^{1/t}$. This can be done by setting the first derivative to zero. In particular, $f'(t) = 1 - (n^{1/t} \log n)/t^2$; setting this to zero yields $n^{1/t} \log n = t^2$, i.e., $$(\log n)/t + \log \log n = 2 \log t.$$

Now the problem is how to solve the above equation for $t$. Note the left-hand side is a decreasing function in $t$ and the right-hand side is an increasing function in $t$. If $t=1$, the left-hand side is greater than the right-hand side. If $t=n$, the right-hand side is greater than the left-hand side. So there is a unique solution for $t$, which is between 1 and $n$. We can use binary search to find that solution.


A couple of related results are listed here just for fun.

The selected $t$ is equal to $\frac{\log n}{\log\log n}$ asymptotically..

The minimum running time is $\Theta(\frac{n\log n}{\log\log n}).$

$\endgroup$
2
  • $\begingroup$ Excellent answer! $\endgroup$ Mar 20 '20 at 22:34
  • $\begingroup$ Amazing answer, thank you. English is not my native language, so I was confused by the wording indeed, as originally I have tried to find the first derivative :) $\endgroup$
    – Valeria
    Mar 21 '20 at 0:18
2
$\begingroup$

You want to find $t$ that minimizes $f(t)=t+n^{1/t}$. This can be done by setting the first derivative to zero. In particular, $f'(t) = 1 - (n^{1/t} \log n)/t^2$; setting this to zero yields $n^{1/t} \log n = t^2$, i.e., $(\log n)/t + \log \log n = 2 \log t$. Solving that analytically for $t$ looks tedious but perhaps you can obtain an approximation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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