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
    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:


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

And then I find the following in many math textbooks:


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.

  • $\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, 2014 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, 2014 at 15:26
  • 1
    $\begingroup$ It will help readers of your questions if clarifications are incorporated into the question. $\endgroup$
    – Jay
    Feb 12, 2014 at 15:36
  • $\begingroup$ @Jay, which clarifications would you like? $\endgroup$
    – Jay
    Feb 12, 2014 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, 2014 at 15:38

1 Answer 1


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

  • $\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, 2014 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, 2014 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, 2014 at 23:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .