Determine the time complexity of the following recursive function by deriving a recurrence relation, solving the relation, proving the correctness of the solution, and finding its big-O notation.

String f2(String x, char c)

{

if (x.length() == 0)

return x;

if (x.charAt(0) == c)

return f2(x.substring(1), c);

else

return x.charAt(0) + f2(x.substring(1), c);

}

The part I'm having trouble with is deriving a recurrence relation from this algorithm. If you could show a step by step of that, it would be much appreciated thank you.