My friend told me about a sorting algorithm she designed that was intentionally bad. We were trying to figure out the big-O runtime, but we quickly realized it would be very difficult. We were, however, able to find a recurrence relation for the run-time to sort an array of size n:
$f(n) = 2*(2*f(\lceil n/2 \rceil) + f(n-2)) + 1 \\ \quad\quad = 4*f(\lceil n/2 \rceil) + 2*f(n-2) + 1, \quad\quad f(0) = 0, \quad f(1) = 0$
However, we have no idea how to turn this into a non-recursive function. Ultimately, we only need the big-O (or more strictly speaking, big-Theta) bounds on f(n). However, the master theorem definitely does not apply, as we are not dividing work into equal-sized portions. It also doesn't really fit any other sort of pattern that I know of for solving recurrence relations. Any help for solving this would be appreciated.