Runtime of Divide and Conquer Flavored Bogo Sort

Question

Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively.

https://en.wikipedia.org/wiki/Bogosort.
Input: An unsorted array A[1...n].
Output: A sorted array.

Let's remind ourselves of why normal Bogo Sort's runtime is O(n!).

Let's say we were to randomly guess the smallest element of an array. What are our odds of guessing right? Our odds would be 1/n of course. Let's say we guessed right! Now let's try to randomly guess the second smallest element of an array, after guessing the first right. What are our odds of guessing right? Our odds would be 1/(n-1) of course.

$$\frac{1}{n}*\frac{1}{n-1}*\frac{1}{n-2}\; * \;... \;*\; \frac{1}{n-n+1}$$ Expectation is n!

Let's use a Divide and Conquer strategy on Bogo Sort to improve the runtime. We will use a modified Merge Sort to achieve this. We recall that merge sort merges two sorted arrays recursively. Can Bogo Sort take advantage of the fact that we are merging two already sorted arrays? Let's say we were to randomly guess the smallest element of two sorted arrays. We know that the smallest element of both can only ever be the first element of one of these two arrays. If we randomly guess from just the first two smallest elements in each array, what are our odds of guessing right? Our odds would be 1/2. This sounds better than 1/n, but let's look at an example recurrence tree.

Example Recurrence Tree:
n = 4     brackets [ ] represent a merge being performed.

$$[\frac{1}{2}*\frac{1}{2}*\frac{1}{2}*\frac{1}{2}]$$ $$[\frac{1}{2}*\frac{1}{2}]\;+\;[\frac{1}{2}*\frac{1}{2}]$$ $$[\frac{1}{2}]+[\frac{1}{2}]+[\frac{1}{2}]+[\frac{1}{2}]$$

[Depth 0] Expectation is 16
[Depth 1] Expectation is 4 + 4 = 8
[Depth 2] Expectation is 1 + 1 + 1 + 1 = 4

Note, that in our base case we only need sort two values, guess between two values, a total of n times. From the above, we see the expected runtime of D&Q Bogo Sort:

Runtime: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ Recurrence: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$ i++ each recurrence

I need help confirming the runtime. My assumption originally was that the runtime is simply O(2^n). However, I believe I need a log( ) in there somewhere. I am unsure how to apply the Master Theorem to O(2^n) in my hypothesized recurrence:

$$2T(\frac{n}{2}) + O(2^n)$$

We have successfully reduced Bogo Sort from factorial runtime to exponential runtime using divide and conquer. Let me know how I can improve my analysis.

Answer 1

The solution to the recurrence $T(n) = 2T(n/2) + O(2^n)$ is $T(n) = O(2^n)$.