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