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

Question

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.

Answer 1

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