Reccurrence equation and finding suitable algorithm
I'm given the following recurrence equation:
$$\begin{align*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\ T(n) &= T((n+1)/2) + 1 && \text{when $n > 1$ is odd.} \end{align*}$$
The problems I have are the following:
1) What does $T(1) = 0$ mean when it comes to writing computer program? It cannot be
return some_constant;
because this gives the complexity of $T(1) = 1$. Am I right?
2) I'm supposed to find an algorithm whose time complexity can be described using the given equation. I was thinking of Fast Power algorithm, because it has the same $O(n) = \log(n)$, but it's described differently:
$$\begin{align*} T(1) &= 1\\ T(n) &= T(n/2) + 1 &&\text{when $n > 1$ is even}\\ T(n) &= T((n-1)/2) + 1 &&\text{when $n > 1$ is odd.} \end{align*}$$
algorithm-analysis recurrence-relation
threazthreaz
$\begingroup$ It seems like they made a mistake. $\endgroup$ – Yuval Filmus Jan 6 '16 at 22:07
1) It doesn't mean anything, for two reasons:
First of all, it's important to distinguish between an algorithm vs the running time of an algorithm. $T(\cdot)$ is not an algorithm; it's a function. For instance, $T(n)$ might be the running time of a computer program, as a function of the size of its input, but it's not the program itself. Anyway, $T(n)$ is just a mathematical function: if it is intended to represent the running time of some algorithm, that should be stated explicitly.
Second, every algorithm needs to take at least at least one step, so the running time always has to be at least one: it can never be zero. Therefore, it doesn't make sense to have a running time of zero. This might be a bit of a quibble/nitpick.
2) I suggest you do a bit more practice with the reverse: given a simple algorithm, work out a recurrence relation for its running time. Once you feel like you're able to do that confidently, you'll probably find this exercise easy.
See also our reference question, How to come up with the runtime of algorithms?. There's also a more advanced, sophisticated treatment at Is there a system behind the magic of algorithm analysis?.
D.W.♦D.W.
Not the answer you're looking for? Browse other questions tagged algorithm-analysis recurrence-relation or ask your own question.
Is there a system behind the magic of algorithm analysis?
How to come up with the runtime of algorithms?
How to go from a recurrence relation to a final complexity
How long does the Collatz recursion run?
Why does the recurrence equation for QuickSort consider all the elements in the array?
Time complexity of the fast exponentiation method
Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution
Show a predicate is primitive recursive
Error solving the next recurrence: $T(n)=7T(n/2)+n^2$