# How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?

Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $$n$$ is odd, it sorts using Bubble Sort and for even $$n$$ it uses Merge Sort. How do we perform the worst-case time complexity analysis for this algorithm?

The context in which this question came about is when I was going through the analysis of MAX-HEAPIFY algorithm given in CLRS(3rd edition) on page 154. In the worst-case analysis, the author had assumed some arbitrary input size $$n$$ and then concluded that the worst case occurs when the bottom-most level of the heap is exactly half full. This threw me off since in various texts and articles, $$n$$ is assumed to be fixed when performing the worst case analysis(and even for best or average cases for that matter) and that the number of elements at the bottom-most level of a heap of $$n$$ nodes is fixed. In that light, I concocted this algorithm so as to have the worst case dependent on $$n$$.

My intuition tells me that the worst case time complexity for this algorithm is $$\mathcal O(n^2)$$ since that's the worst case runtime for Bubble Sort. But I want to know the precise mathematical formulation of the worst-case time complexity analysis for any algorithm. Any insight would be much appreciated.

Let $$f(n)$$ the maximum number of elementary operations performed by the algorithm when the number of elements to sort is $$n$$.

An upper bound to the worst-case complexity of the algorithm is $$O(n^2)$$ since there exists some $$n_0$$ and some constant $$c>0$$ such that for every $$n \ge n_0$$, $$f(n) \le c n^2$$.

Moreover, given some other function $$g(n) = o(n^2)$$ it is false that $$f(n) \in O(g(n))$$ since for all $$c>0$$, there always exists a sufficiently large $$n$$ for which $$f(n) \ge c g(n)$$. In this sense, $$O(n^2)$$ is the smallest asymptotic upper bound you can hope to obtain.

Notice however that with this choice of $$f(n)$$ it is not true that $$f(n) = \Omega(n^2)$$ according to Knuth's definition of big Omega, while it is true in the Hardy–Littlewood definition. The "problem" here is that $$f(n)$$ is not monotonically non-decreasing, while the functions considered in algorithm analysis usually are.

Of course you can define $$F(n) = \max_{0 \le n' \le n} f(n')$$ to get a monotonically non-decreasing function, which is probably what you have in mind when you think of the worst-case running time of the algorithm.

Then you have: $$F(n) = O(n^2)$$ and $$F(n)= \Omega(n^2)$$ showing that $$F(n) = \Theta(n^2)$$.

• Oh wow this cleared up a lot of confusion I had! Basically $f(n)$ will be a piece-wise function where for odd $n$, $f(n)\in O(n^2)$ and for even $n$, $f(n)\in O(n\log n).$ So overall $f(n)\in O(n^2)$. Thinking in terms of a concrete $f(n)$ rather than asymptotic class really helped me here! Thanks for such an elaborate answer! Jan 12, 2021 at 18:47