2
$\begingroup$

The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows:

**Algorithmic recurrences

[...] A recurrence is algorithmic, if for every sufficiently large threshold constant $n_0 > 0$, the following two properties hold:

  1. For all $n < n_0$, we have $T(n) = \Theta(1)$
  2. For all $n \geq n_0$, every path of recursion terminates in a defined base case within a finite number of recursive invocations.

The following justification is then provided for the first property:

[...] The first property says that there exists constants $c_1$, $c_2$ such that $0 < c_1 \leq T(n) \leq c_2$ for $n < n_0$. For every legal input, the algorithm must output the solution to the problem it's solving in finite time (see Section 1.1). Thus, we can let $c_1$ by the minimum amount of time to call and return from a procedure, which must be positive since, because machine instructions need to be executed to invoke a procedure. The running time of an algorithm may not be defined for some values of $n$ if there are no legal inputs of that size, but it must be defined for at least one, or else the "algorithm" doesn't solve any problem. Thus, we can let $c_2$ be the algorithm's maximum running time on any input of size $n < n_0$, where $n_0$ is sufficiently large that the algorithm solves at least one problem of size less than $n_0$.

I'm not sure I follow the reasoning for $c_1$ and $c_2$ being the minimum and maximum base case running times, respectively.

For $c_1$, the authors say, "For every legal input, the algorithm must output the solution to the problem it's solving in finite time (see Section 1.1). Thus, we can let $c_1$ by the minimum amount of time to call and return from a procedure."

  • I don't see the connection between the alogrithm completing in finite time and $c_1$ being the minimum running time. Doesn't this reasoning makes more sense for $c_2$ being the maximum running time? Since if an algorithm by definition finishes in a finite amount of time, then there must be some ceiling to the running time.

For $c_2$, the authors say, "The running time of an algorithm may not be defined for some values of $n$ if there are no legal inputs of that size, but it must be defined for at least one, or else the "algorithm" doesn't solve any problem. Thus, we can let $c_2$ be the algorithm's maximum running time on any input of size $n < n_0$, where $n_0$ is sufficiently large that the algorithm solves at least one problem of size less than $n_0$."

  • I don't understand why there being at least one input of size $< n_0$ implies that $c_2$ is the maximum running time. This argument seems to make more sense for $c_1$ being the minimum running time, since if there is at least one problem of size $< n_0$, then it must take some non-zero amount of between $c_1$ and $c_2$.

I would be grateful for any help on this, as I cannot find anything on algorithmic recurrences outside of the book.

$\endgroup$
1
  • $\begingroup$ The condition $\forall n<n_0:T(n)=\Theta(1)$ is a notational abuse, because $\Theta(1)$ implies a condition on all $n>m_0$. $\endgroup$
    – user16034
    Jun 9, 2023 at 13:34

2 Answers 2

2
$\begingroup$

The 1st property is referring to the time needed by the recursive algorithm to solve a problem instance with size $n<n_0$. Under this case the algorithm can directly solve the problem, i.e. no recursion needed. They are then trying to show that the time needed for this must be constant, because the size of the instance is bounded from above by a constant $n_0$. And that's where the two constants comes into play.

The reason for having two constants $c_1$ and $c_2$ is to prove that the time needed is $\Theta(1)$. Please review the definition of $\Theta$ for this.

The algorithm must terminate after some time otherwise it will not solve the problem. Now as mentioned above we are only considering constant size instances. Since the running-time is based on the size of the input, the running-time must be constant (no matter how long it takes, the algorithm is only processing constant number of things) . Among all the possible instances with constant size, one of them will need the least amount of time. This gives you $c_1$.

Now for the other case, it's almost the same idea except you just select the instance that will give the largest running-time and you'll get $c_2$. As noted in their explanation, there must be at least one instance that gives the max time, which again must take constant time. This instance exist since the algorithm needs to be able to solve the problem.

As a final note, just in case only one instace fits the size restriction, then it's still acceptable that $c_1 =c_2$.

$\endgroup$
1
  • $\begingroup$ Any terminating algorithm executed on an input of bounded size $n<n_0$ is said to run in constant time (abusively written $\Theta(1)$). So in fact there is nothing to prove. $\endgroup$
    – user16034
    Jun 9, 2023 at 13:53
2
$\begingroup$

If there is at least one $n<n_0$ such that there is a legal input, then obviously the running time can be bracketed as

$$c_{\min}\le T(n)\le c_{\max}$$ where the minimum and maximum are taken over all legal inputs (for all $n<n_0$).

Obviously, the lower bound is itself bounded by the time for an empty function, let $c_1$, and

$$c_1\le c_{min}.$$ The author also denotes $c_{\max}$ as $c_2$. Note that $c_1$ can be known a priori, while $c_2$ depends on the studied algorithm.

$\endgroup$
1
  • $\begingroup$ I personally see little benefit of defining $c_1$ this way, as this makes the reasoning a little asymmetric (which puzzles the OP). $\endgroup$
    – user16034
    Jun 9, 2023 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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