1
$\begingroup$

We are to determine a recurrence relation for a recursive algorithm.

Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person remains.

The code is given as:

 def josephus( n, k):
  if n ==1:
    return 1
  else:
    return ((josephus(n-1,k)+k-1) % n)+1

So I am assuming that the portion after the final return is the recurrent portion? Because that defines the problem recursively. So:

T(n,k)=[T(n-1,k)+k+1] + 1

But my professor gives T(n)=T(n-1)+C as the recurrence relation for a factorial n!. Then using that idea, I get the recurrence relation:

T(n)=T(n-1)+O(1)

With the O(1) derived from the if n == 1 fragment.

And then I find the following in many math textbooks:

T(2n)=2T(n)-1
T(2n+1)=2T(n)+1

But it seems this is only valid for when k=2.

This is where I am confused. I don't know which is the recurrence relation and what T(n) is supposed to mean. What is a recurrence relation T(n)? It is obvious that this algorithm is a linear upperbound by simply looking at the code.

$\endgroup$
6
  • $\begingroup$ What is your algorithm supposed to return? What is the recurrence relation you are trying to get for — is is to determine the time complexity of the algorithm (I reckon so), or a closed-form formula for its output, or something else? $\endgroup$
    – Clement C.
    Feb 12 '14 at 15:23
  • $\begingroup$ Hi @ClementC. The algorithm is supposed to return the "survivor". And the recurrence relation is to determine the time complexity. $\endgroup$
    – Jay
    Feb 12 '14 at 15:26
  • 1
    $\begingroup$ It will help readers of your questions if clarifications are incorporated into the question. $\endgroup$
    – Jay
    Feb 12 '14 at 15:36
  • $\begingroup$ @Jay, which clarifications would you like? $\endgroup$
    – Jay
    Feb 12 '14 at 15:38
  • $\begingroup$ Then, assuming the code is correct (I'm too lazy to prove or even consider correctness), the recurrence relation is just $$T_k(n) = T_k(n-1)+ C$$ for some constant $C$: $k$ is not involved in the time complexity, it is just a fixed parameter, and each recursive call with argument $2\leq m\leq n$ does (a) a constant number of elementary operations and (b) a recursive call with argument $m-1$. $\endgroup$
    – Clement C.
    Feb 12 '14 at 15:38
1
$\begingroup$

For your josephus problem, the recursion has one function call for each of n, n-1, n-2,...,1, so that $T(n)=O(n)$ is the expected outcome.

The $T(2n)=c\cdot T(n)+O(1)$ behavior occurs typically for divide and conquer algorithms like efficient integer powers, Karatsuba multiplication and other fast multiplication algorithms, FFT. There you can consider the numbers $c^{-n}T(2^n)$ and find that they most often amount to a constant, so that $T(2^n)=O(c^n)$ or $T(N)=O(N^{\log_2c})$. For example in Karatsuba multiplication you get to replace one full multiplication by 3 half length multiplications, so $c=3$.


The problem of the formulation of your question is that you used T(n) for the iteration function. But in the context of complexity of algorithms, $T(n)$ is almost exclusively reserved for some counting of the run time for input (of size) $n$, so better use J(n) or F(n) for the iteration function.

So yes, if F(2n) and F(2n+1) are computed from F(n), then $T(2n)=T(n)+c$ and $T(n)=O(log_2(n))$.

$\endgroup$
3
  • $\begingroup$ so the Josephus Problem follows divide and conquer to my understanding, because after every "round" there are n/k less people standing. So would this indicate that T(2n)=c*T(n)+O(1)? $\endgroup$
    – Jay
    Feb 12 '14 at 19:25
  • $\begingroup$ No, where do you see that? Josepus(n,k) calls Josephus(n-1,k), this is a simple countdown from n to 1. Or said in a different way, after each round there is one participant less, k only determines which participant is leaving in each round. $\endgroup$ Feb 12 '14 at 23:37
  • $\begingroup$ Please edit your question so that the iteration function is not labeled with T. Yes, in the implementation where each function call eliminates n/k participants, there will be O(log(n)) calls of the recursion function. The english wikipedia article is not very clear there, the german one is better, but too short. $\endgroup$ Feb 12 '14 at 23:50

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.