0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Turned out to be pretty close to 25*2^(n/2) when I plotted it in Maple. Thanks for the help! $\endgroup$ – Sam Walko Aug 23 '20 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.