1. **Problem Statement:** We have $n$ items to sort using BucketSort with $k = \frac{n}{\log \log n}$ buckets. The input distribution is non-uniform: half the items are uniformly distributed in $[0, \frac{1}{3}]$ and the other half in $(\frac{1}{3}, 1]$. We use heap-sort to sort items within each bucket. We want to find the expected running time. 2. **Recall BucketSort running time:** - BucketSort distributes $n$ items into $k$ buckets. - Expected time to distribute is $O(n)$. - Sorting each bucket takes time depending on the number of items in that bucket. - Total time is $O(n + \sum_{i=1}^k T_i)$ where $T_i$ is the time to sort bucket $i$. 3. **Key insight:** - If items are uniformly distributed, each bucket gets about $\frac{n}{k}$ items. - Sorting each bucket with heap-sort takes $O(m_i \log m_i)$ where $m_i$ is the number of items in bucket $i$. - Total sorting time is $\sum_{i=1}^k O(m_i \log m_i)$. 4. **Distribution of items:** - Half the items ($\frac{n}{2}$) lie in $[0, \frac{1}{3}]$. - Half the items ($\frac{n}{2}$) lie in $(\frac{1}{3}, 1]$. 5. **Buckets and intervals:** - Buckets are evenly spaced over $[0,1]$. - Number of buckets: $k = \frac{n}{\log \log n}$. - Bucket width: $\frac{1}{k} = \frac{\log \log n}{n}$. 6. **Buckets in $[0, \frac{1}{3}]$:** - Number of buckets in this interval: approximately $\frac{1/3}{1/k} = \frac{k}{3} = \frac{n}{3 \log \log n}$. - Items in this interval: $\frac{n}{2}$. - Average items per bucket here: $\frac{n/2}{k/3} = \frac{n/2}{n/(3 \log \log n)} = \frac{3}{2} \log \log n$. 7. **Buckets in $(\frac{1}{3},1]$:** - Number of buckets: $k - \frac{k}{3} = \frac{2k}{3} = \frac{2n}{3 \log \log n}$. - Items: $\frac{n}{2}$. - Average items per bucket: $\frac{n/2}{2k/3} = \frac{n/2}{2n/(3 \log \log n)} = \frac{3}{4} \log \log n$. 8. **Sorting time per bucket:** - Using heap-sort, sorting $m$ items takes $O(m \log m)$. - For buckets in $[0, \frac{1}{3}]$, sorting time per bucket is $O(\log \log n \cdot \log(\log \log n))$. - For buckets in $(\frac{1}{3},1]$, sorting time per bucket is $O(\log \log n \cdot \log(\log \log n))$ as well. 9. **Total sorting time:** - Number of buckets in $[0, \frac{1}{3}]$ is $\frac{k}{3} = \frac{n}{3 \log \log n}$. - Number of buckets in $(\frac{1}{3},1]$ is $\frac{2k}{3} = \frac{2n}{3 \log \log n}$. - Total sorting time: $$ \frac{n}{3 \log \log n} \cdot O(\log \log n \cdot \log(\log \log n)) + \frac{2n}{3 \log \log n} \cdot O(\log \log n \cdot \log(\log \log n)) = O(n \log(\log \log n)) $$ 10. **Total expected running time:** - Distribution time: $O(n)$. - Sorting time: $O(n \log(\log \log n))$. - Since $\log(\log \log n)$ grows very slowly, the dominant term is $O(n \log(\log \log n))$. 11. **Matching with options:** - None of the options explicitly list $\theta(n \log(\log \log n))$. - The closest is option (i) $\theta(n \log \log \log n)$ which matches the derived complexity. **Final answer:** (i) $\theta(n \log \log \log n)$