# Trying to find the big-O runtime of an algorithm

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.

It should be dominated by the second term, i.e. $$2 f(n - 2)$$.
Thus we may define $$g(n) = f(n) / 2^{n/2}$$ and we will have: $$g(n) = 4\times g(n / 2)\times 2^{- n/4} + g(n - 2) + 2^{-n/2}.$$ Here I have omitted the $$\lceil\cdot\rceil$$ for simplicity.
Since the geometric series $$\sum_n2^{-n/4}$$ and $$\sum_n2^{-n/2}$$ converge, it is easy to show that the sequence $$g(n)$$ is bounded, and therefore we have $$f(n) = \Theta(2^{n / 2})$$.